题解 P1281 【书的复制】

HoshiuZ · 2019-11-22 00:12:19 · 题解

定义f[i][j]表示将前j本书分给i个人的最短复制时间，那么易得

其中

具体含义：将前j本书分给i个人的最短复制时间，等同于将前k本书分给i-1个人的最短复制时间与将第k+1到第j本书分给一个人的最短复制时间的最大值，枚举k，取这其中的最小值。

这样复制最后的复制时间即为f[k][m]。接着的操作就是如何判断每个人的抄的书。题目中说，如果有多解，则尽可能让前面的人少抄写。因此可以采用贪心，从末尾开始向前加，加到不能再加了时（即再加后就超过了f[k][m]）就把这一组分给一个人。这样递归输出即可。

#include<bits/stdc++.h>

using namespace std;

int m,k,page[510],dp[510][510];

void printp(int x,int to) {
    if(!to) return ;
    int sum=0,t=1;
    for(int i=to;i>=1;i--) {
        sum+=page[i];
        if(sum>x) {
            sum-=page[i];
            t+=i;
            break;
        }
    }
    printp(x,t-1);
    cout<<t<<" "<<to<<endl;
}

int main() {
    memset(dp,127,sizeof(dp));
    cin>>m>>k;
    dp[1][0]=0;
    for(int i=1;i<=m;i++) {
        cin>>page[i];
        dp[1][i]=dp[1][i-1]+page[i];
    }

    for(int i=2;i<=k;i++) {
        for(int j=1;j<=m;j++) {
            for(int k=1;k<j;k++) {
            dp[i][j]=min(dp[i][j],max(dp[i-1][k],dp[1][j]-dp[1][k]));
            }
        }
    }

    printp(dp[k][m],m);

    return 0;
}