luoguP1281 书的复制

链接

https://www.luogu.org/problemnew/show/P1281

思路

简单dp，输出方案。
很明显dp记录路径对不对？
恭喜你死了。
求出dp值，倒叙贪心取最长

错误

好久之前咕咕的题目
下载数据才看出来不能记录路径

代码

#include <bits/stdc++.h>
using namespace std;
const int N=507;
const int inf=0x3f3f3f3f;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='0') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,K,sum[N],f[N][N],stak[N],top;
vector<pair<int,int> > a;
int main() {
    n=read(),K=read();
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+read();
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int k=1;k<=K;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=i;++j)
                f[i][k]=min(f[i][k],max(f[j-1][k-1],sum[i]-sum[j-1]));
    int r=n,tot=0;
    for(int i=n;i>=1;--i) {
        tot+=sum[i]-sum[i-1];
        if(tot>f[n][K]) {
            a.push_back(make_pair(i+1,r));
            tot=sum[i]-sum[i-1];
            r=i;
        }
    }
    if(tot) a.push_back(make_pair(1,r));
    for(vector<pair<int,int> >::iterator it=a.end()-1;it!=a.begin()-1;it--)
        printf("%d %d\n",it->first,it->second);
    return 0;
}