OI党坚毅的步伐|Codevs3162抄书问题题解 OI党坚毅的步伐|动态规划

题目

题目来源

http://codevs.cn/problem/3162/

题目描述 Description
现在要把M本有顺序的书分给K个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
输入描述 Input Description
第一行两个整数M、K；（K<=M<=100）
第二行M个整数，第i个整数表示第i本书的页数。
输出描述 Output Description
共K行，每行两个正整数，第i行表示第i个人抄写的书的起始编号和终止编号。K行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
样例输入 Sample Input
9 3
1 2 3 4 5 6 7 8 9
样例输出 Sample Output
1 5
6 7
8 9

题解

自己对划分型DP一点感觉都没有，一开始把阶段和状态弄反了。。。竟然还能过6个点。。。
把书的页数a[i]预处理出来一个前缀和数组w[i]；
以人数为阶段，书数为状态，i个人j本书的状态是由i-1个人p本书的状态转移过来：
f[i][j]=minj?1p=1{max{f[i?1][p],w[i]?w[p]}} ；
初始化f[1][i]=w[i]。
【OI党坚毅的步伐|Codevs3162抄书问题题解】输出方案时，要求前面的人抄的页数少，那就让后面的人抄的页数多，边递归边贪心，只要让当前的人抄的页数不大于f[k][m]即可。

Code

#include #include #include #define N 105 using namespace std; int m, k, f[N][N], w[N], a[N]; void getans(int x, int y) { if(y == 0) return; if(y == 1) { printf("1 %d\n", x); return; } int t = x; for(int i = a[x]; i + a[t - 1] <= f[k][m]; --t) i += a[t - 1]; getans(t - 1, y - 1); printf("%d %d\n", t, x); } int main() { memset(f, 0x3f, sizeof(f)); scanf("%d%d", &m, &k); for(int i = 1; i <= m; ++i) { scanf("%d", &a[i]); f[1][i] = w[i] = a[i] + w[i - 1]; } for(int i = 2; i <= k; ++i) for(int j = 1; j <= m; ++j) { for(int p = 1; p < j; ++p) { if(f[i][j] > max(f[i - 1][p], w[j] - w[p])) { f[i][j] = max(f[i - 1][p], w[j] - w[p]); } } } getans(m, k); return 0; }