求助，一道难难难写的动态规划题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1895 天前的主题，其中的信息可能已经有所发展或是发生改变。

题目描述
在一条直线上有 n 处地方，从左到右依次编号为 1, 2, …, n，每处地方都有一定量的树木，每处地方的单位量树木运送单位距离都需要一定的费用，例如在 1 处有数量为 a 的树木，单位量的树木运送单位距离的费用是 b，那么把这么多树木一共运送 c 的距离所需要的费用为 a*b*c。现在需要把这 n 处地方的树木送往加工中心处理，为了使得路径单一，所有地方的树木只能向右边（编号较大的地方的方向）运送，已知第 n 处的地方已经存在了一个加工中心。为了减少树木运送的费用，在这条路径上最多可以添加 k 个加工中心，使得总运费最少。问最小的运费是多少？

解答要求
时间限制：2000ms, 内存限制：64MB
输入
输入数据一共包括 4 行，第 1 行输入 n 和 k(2<=n<=10000, 1<=k<=min(200, n-1))，表示 n 处地方，最多添加 k 个加工中心。第 2 行输入 n 个正整数，表示每个地方的树木总量，第 3 行输入 n 个正整数，表示每个地方单位数量单位距离运送的费用。第 4 行输入 n-1 个正整数，表示从左到右相邻两个地方的距离。除 n 以外，所有的数字都<=300。

输出
输出一行一个整数，表示最小的运费。

样例
输入样例 1 复制

3 1
1 2 3
3 2 1
2 2
输出样例 1

6

提示
Carry_tree 简单题解

不难证明，加工厂只能建在节点上
比较容易想到状态方程：dp[k][n] = min{0<=i<n}(dp[k - 1][i] + delta(i + 1, n))
其中 delta(i + 1, n)表示为从 i + 1 到 n 的所有树木运送到第 n 号节点的耗费总和
复杂度 O(k*n*n)，会超时，需要优化。
采用斜率优化，我们令设几个变量。
sum[n]表示从 1~n 的所有的树木搬到 n 号节点所需要的代价总和
a[n]表示从 1~n 的所有的树木所搬运单位路程所需的代价
d[n]表示从 1~n 的距离
那么 delta(i + 1, n) = sum[n] - sum[i] - a[i] * (d[n] - d[i])
所以原方程式化为 dp[k][n] - sum[n] = min{0<=i<n}(dp[k - 1][i] - sum[i] + a[i] * d[i] - a[i] * d[n])
因为 a[i]单调递增，因而采用斜率优化。

树木

SUM

运送

样例

2 条回复 • 2019-09-16 22:17:14 +08:00

chunwang1995

2019-09-16 21:07:59 +08:00

尽力了，求问 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...
}
```

chunwang1995

2019-09-16 22:17:14 +08:00

```
#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;
}
```