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