书的复制 动规，贪心

题目链接：https://www.luogu.org/problemnew/show/P1281

分析：用dp[i][j]来表示前i个人分j本书所需的最短时间

我们可以利用第三层u来实现状态转移，u用来表示前i-1人抄写的最后一本书

状态转移方程式为：dp[i][j]=min(dp[i][j],max(dp[i-1][u-1],sum[j]-sum[u-1]))   sum数组为前缀和数组

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const ll maxn=510;
const double pi=acos(-1);
const int mod=10000;
int a[maxn],sum[maxn];
int dp[maxn][maxn];
void print(int x,int ans){
    if(!x)return ;
    for(int i=x;i>=0;i--){
        if(i==0||sum[x]-sum[i-1]>ans){
            print(i,ans);
            printf("%d %d
",i+1,x);
            break;
        }
    }
}
int main(){
    int m,k;scanf("%d%d",&m,&k);
    fill((int *)dp,(int *)dp+510*510,inf);
    for(int i=1;i<=m;i++){
    scanf("%d",&a[i]);
    sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=m;i++){
        dp[1][i]=sum[i];
    }
    for(int i=2;i<=k;i++){
        for(int j=i;j<=m;j++){
            for(int u=i;u<=j;u++){
                dp[i][j]=min(dp[i][j],max(dp[i-1][u-1],sum[j]-sum[u-1]));
            }
        }
    }
    //cout<<dp[k][m]<<endl;
    print(m,dp[k][m]);
    return 0;
}