题解 P1281 【书的复制】

Dry_ice · 2020-07-18 15:30:09 · 题解

动态规划就是：

设字母，写式子。你怎么讲，我怎么写。

看有很多 dalao 写了二分，我来一波基础动规。

整体思路：动态规划

具体步骤（状态的设置与应用）

1. 定义状态：设 F_{i,j} 表示前 i 个人分 j 本书的最短时间。

2. 答案位置：根据状态 F_{i,j} 的含义，我们可以知道最短用时是 F_{k,m} 。

3. 状态转移

仔细阅读题目，我们会发现所用时间并不是所有人用时之和，而是所有人中用时最多的那个人的用时。

所以转移方程也就出来了：

4. 初始化（简单却不可省略）

打印答案

只需要写一个 void 类型的 print 递归函数利用贪心思想进行 倒序递归，正序打印 。

CODE

#include <stdio.h>
#include <string.h>
#include <algorithm>
int m,k;
int c[505], s[505];
int f[505][505];
inline void init() {
    memset(f, 127 / 3, sizeof f);
    scanf("%d %d", &m, &k);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &c[i]);
        s[i] = s[i - 1] + c[i];
        f[1][i] = s[i];
    }
}
inline void work() {
    for (int i = 2; i <= k; ++i)
        for (int j = 1; j <= m; ++j)
            for (int l = 1; l < j; ++l)
                if (std:: max(f[i - 1][l], s[j] - s[l]) < f[i][j]) 
                    f[i][j] = std:: max(f[i - 1][l], s[j] - s[l]);
}
inline void print(int i, int j) {
    if(j == 0) return;
    if(j == 1) {
        printf("1 %d\n",i);
        return ;
    }
    int p = i, q = c[i];
    while(q + c[p - 1] <= f[k][m]) {
        q += c[p - 1];
        --p;
    }
    print(p - 1, j - 1);
    printf("%d %d\n", p, i);
}
int main(void) {
    init();
    work();
    print(m, k);
    return 0;
}

（不要抄题解

The end. Thanks.