题解 P1281 【书的复制】

hongzy · 2017-12-21 13:48:11 · 题解

区间型DP + 贪心

用f[i][j]表示i个人复制前j本书的最短时间

穷举最后一个人从哪开始复制,k是最后一个人开始复制的位置

f[i][j] = min(f[i][j], max(f[i-1][k-1], Sum[j] - Sum[k-1]));

即移到i个人复制前j本书的最短时间是子问题：

"i-1个人复制前k-1的书，第k个人复制从k到j的书."

的最优解.

输出是贪心，递归输出.

#include <iostream>
#include <cstdio>
using namespace std;

int f[501][501]; //i人j书复制的最短时间
int A[501], Sum[501];
int N, K;

void Print(int x, int Ans) {
    if(!x) return;
    for(int i=x; i>=0; i--) {
        if(Sum[x] - Sum[i-1] > Ans || !i) {
            Print(i, Ans);
            printf("%d %d\n", i+1, x);
            break;
        }
    }
}

int main() {
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++) scanf("%d", &A[i]);
    for(int i=1; i<=K; i++)
        for(int j=1; j<=N; j++)
            f[i][j] = 1e9;
    for(int i=1; i<=N; i++) Sum[i] = Sum[i-1] + A[i], f[1][i] = Sum[i];
    for(int i=2; i<=K; i++)
        for(int j=1; j<=N; j++) 
            for(int k=2; k<=j; k++)  //枚举最后一个人的复印的开始位置
                f[i][j] = min(f[i][j], max(f[i-1][k-1], Sum[j] - Sum[k-1]));
    Print(N, f[K][N]);
    return 0;
}