V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
chunwang1995
V2EX  ›  算法

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

  •  
  •   chunwang1995 · 2019-09-16 21:07:14 +08:00 · 4004 次点击
    这是一个创建于 1655 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目描述
    在一条直线上有 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]单调递增,因而采用斜率优化。
    
    2 条回复    2019-09-16 22:17:14 +08:00
    chunwang1995
        1
    chunwang1995  
    OP
       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
        2
    chunwang1995  
    OP
       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;
    }
    ```
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1268 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 17:52 · PVG 01:52 · LAX 10:52 · JFK 13:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.