chunwang1995 最近的时间轴更新
chunwang1995

chunwang1995

V2EX 第 294441 号会员,加入于 2018-02-26 16:03:34 +08:00
求助,一道难难难写的动态规划题
算法  •  chunwang1995  •  2019-09-16 22:17:14 PM  •  最后回复来自 chunwang1995
2
一个 Go 的指针问题求助
Go 编程语言  •  chunwang1995  •  2019-07-24 10:09:38 AM  •  最后回复来自 zarte
4
求推荐技术社区
Linux  •  chunwang1995  •  2019-07-22 13:42:39 PM  •  最后回复来自 geekjc
6
V 友们,求推荐正经的操作系统交流社区
Linux  •  chunwang1995  •  2019-07-17 05:34:53 AM  •  最后回复来自 yujincheng08
2
如何有效学习 Powershell
PowerShell  •  chunwang1995  •  2018-10-10 09:32:36 AM  •  最后回复来自 ps1aniuge
12
chunwang1995 最近回复了
2019-09-16 22:17:14 +08:00
回复了 chunwang1995 创建的主题 算法 求助,一道难难难写的动态规划题
```
#define MAX_ROW 11000
#define MAX_COL 210

long long dp[MAX_ROW][MAX_COL];
long long sum[MAX_ROW], dis[MAX_ROW], W[MAX_ROW], val[MAX_ROW], num[MAX_ROW];
int Q[MAX_ROW + MAX_ROW], L, R;

double Slope(long long i, long long j, long long k)
{
return (double)((dp[i][k] - sum[i] + dis[i] * W[i]) - (dp[j][k] - sum[j] + dis[j] * W[j])) / (W[i] - W[j]);
}

void push_node(int idx, int k)
{
while (L < R && Slope(Q[R - 1], Q[R], k) >= Slope(Q[R], idx, k))
R--;
Q[++R] = idx;
}

void pop_node(double S, int k)
{
while (L < R && Slope(Q[L], Q[L + 1], k) <= S)
L++;
}

int main()
{
long long n, k, i, j, a, b, c, u, v, tmp;
scanf("%lld%lld", &n, &k); k++;

for (i = 0; i < n; i++)
scanf("%lld", &val[i]);

for (i = 0; i < n; i++)
scanf("%lld", &num[i]);

for (i = 0; i < n; i++)
W[i] = num[i] * val[i];

for (i = 1; i < n; i++)
W[i] += W[i - 1];

dis[0] = 0;
for (i = 1; i < n; i++) {
scanf("%lld", &tmp);
dis[i] = dis[i - 1] + tmp;
}
sum[0] = 0;
for (i = 1; i < n; i++) {
sum[i] = sum[i - 1] + W[i - 1] * (dis[i] - dis[i - 1]);
dp[i][1] = sum[i];
}
for (j = 2; j <= k; j++) {
L = 0;
R = 0;
Q[0] = 0;
dp[0][j - 1] = 0;
for (i = 1; i < n; i++) {
pop_node(dis[i], j - 1);
int front = Q[L];
dp[i][j] = dp[front][j - 1] + sum[i] - sum[front] - (dis[i] - dis[front]) * W[front];
push_node(i, j - 1);
}
}
printf("%lld\n", dp[n - 1][k]);
return 0;
}
```
2019-09-16 21:07:59 +08:00
回复了 chunwang1995 创建的主题 算法 求助,一道难难难写的动态规划题
尽力了,求问 dp() 里面应该怎么写

```
#include <stdio.h>
#include "securec.h"

typedef struct {
int cost;
int cost_acc;
int distance;
int distance_acc;
int sum;
} pos_t;

int modify(int i, int n);
int dp(int k, int n, int min);

int g_n = 0;
pos_t* g_store = NULL;

int main(void)
{
int k;
if (-1 == scanf_s("%d %d", &g_n, &k)) {
return -1;
}

g_store = (pos_t*)malloc(g_n * sizeof(pos_t));
if (g_store == NULL) {
return -1;
}

for (int i = 0; i < g_n; i++) {
scanf("%d", &(g_store + i)->cost);
}

int temp = 0;
for (int i = 0; i < g_n; i++) {
scanf("%d", &temp);
(g_store + i)->cost *= temp;
if (i != 0) {
(g_store + i)->cost_acc = (g_store + i - 1)->cost_acc + (g_store + i)->cost;
} else {
(g_store + i)->cost_acc = temp;
}
temp = 0;
}

for (int i = 0; i < g_n; i++) {
scanf("%d", &temp);
(g_store + i)->distance = temp;
if (i != 0) {
(g_store + i)->sum = (g_store + i - 1)->sum + (g_store + i - 1)->cost_acc * (g_store + i - 1)->distance;
(g_store + i)->distance_acc = (g_store + i - 1)->distance + (g_store + i - 1)->distance_acc;
} else {
(g_store + i)->sum = 0;
(g_store + i)->distance_acc = 0;
}
temp = 0;
}

#ifdef DEBUG
printf("n: %d, k: %d\n", g_n, k);
for (int i = 0; i < g_n; i++) {
pos_t temp_pos = *(g_store + i);

const char* format = "store[%d]: cost: %d, cost_acc: %d, distance: %d, distance_acc: %d, sum: %d\n";
printf(format, i, temp_pos.cost, temp_pos.cost_acc, temp_pos.distance, temp_pos.distance_acc, temp_pos.sum);
if (i != 0) {
// printf("modify is %d\n", modify(0, i));
}
}
printf("Result is %d\n", dp(k, g_n, -1));
#else
printf("%d\n", dp(k, g_n, -1));
#endif

return 0;
}

inline int modify(int i, int n)
{
int retVal = (g_store + n)->cost_acc * (g_store + i)->distance_acc - (g_store + i)->sum -
(g_store + i)->cost_acc * (g_store + n)->distance_acc + (g_store + n)->sum;
if (i >= n - 1){
return 0;
}
printf("Invoke modify(%d, %d) return (%d)\n", i, n, retVal);
return retVal;
}

inline int dp(int k, int n, int minium)
{
// How to...
}
```
2019-07-16 21:11:16 +08:00
回复了 chunwang1995 创建的主题 Linux V 友们,求推荐正经的操作系统交流社区
自顶一下,求而不得,加过知名 MOOC 的学习群效果不好,望推荐
谢 V 友支持!
2018-09-03 14:46:58 +08:00
回复了 shayuvpn0001 创建的主题 程序员 为什么有了 Git 还需要 ANT/Maven/Gradle?
Maven/Gradle 是 “ Java 工程化”的工具组,正如盖房子一样,只有瓦工或者电工是无法盖成整栋的房子的,而需要“管理工具”粘合各项基本能力,Maven / Gradle 是“工程化”胶水,Git 更像是“开发流程化”胶水。
2018-08-29 13:24:07 +08:00
回复了 chunwang1995 创建的主题 PowerShell 如何有效学习 Powershell
比如自动配置 Windows AD..
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1029 人在线   最高记录 6543   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 892ms · UTC 22:29 · PVG 06:29 · LAX 15:29 · JFK 18:29
Developed with CodeLauncher
♥ Do have faith in what you're doing.