题解 P4852 【yyf hates choukapai】

· · 题解

为了%一波yyf巨佬@ouuan，发一篇题解以示尊敬。

正经一点，这道题虽然套路很平常，但是各种边界还蛮容易搞错的，尤其是最开始f[i][1]那一段和f[s][n]必须也要满足单抽<=d(因为这个疯狂wa，yyfnb)。

另外，与巨佬豪放的展开式码风不同，下面是一份平凡而简短的代码：

CODE:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstring>
#define s c*n+m
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=210000;
int last[N][50],q[N],f[N][50],l,r,n,m,c,d,sum[N],ans,a[N],en,out[N];
int main(){
    n=read();m=read();c=read();d=read();
    register int i,k;
    for(i=1;i<=s;i++)
        a[i]=read();
    for(i=1;i<=s;i++)
        sum[i]=sum[i-1]+a[i];
    for(i=1;i<=d+1;i++)
        f[i][1]=sum[i];
    for(k=2;k<=n;k++)
        {
        l=1;r=0;
        for(i=(k-1)*c+1;i<=s-c+1;i++){
            while(l<=r&&q[l]<i-c-d)l++;
            while(l<=r&&f[i-c][k-1]-sum[i-1]>=f[q[r]][k-1]-sum[q[r]+c-1])r--;
            q[++r]=i-c;
            f[i][k]=f[q[l]][k-1]+sum[i]-sum[q[l]+c-1];
            last[i][k]=q[l];
            if(k==n)if(ans<f[i][k]+sum[s]-sum[i+c-1]&&i>=s-c-d+1){
                ans=f[i][k]+sum[s]-sum[i+c-1];
                en=i;
            };
        }
    }
    cout<<ans<<'\n';
    k=n;
    int now=en,tot=0;
    while(k){
        out[++tot]=now;
        now=last[now][k];
        k--;
    }
    for(i=tot;i>=1;i--)cout<<out[i]<<' ';
    return 0;
}