P4852

· · 题解

P4852 yyf hates choukapai

链接

这道题调了很久，也带给我一些反思，反思写到最后。

1 状态设计

我的状态设计与大部分题解的并不相同，我的状态数会更少一些，设 f_{i,j} 表示一共抽了 j 次，其中，有 i 次是连抽，并且第 j 次抽是连抽。

2 转移

首先，我们在序列的后面加上 c 个 0 ，这样我们就可以强制最后一次是连抽而不影响正确性。

我们枚举前一次连抽是第几次：

f_{i,j}=\max\limits_{\max(j-d-1,0)\le k\le j-1} \{ f_{i-1,k}+sum_{now-c+1}-sum_{last} \}

其中 sum 是前缀和，now 是状态 f_{i,j} 对应的位置，也就是 i\times c+(j-i) ，last 是 f_{i-1,k} 对应的位置，计算方法和左边相同。那么这个就是一个裸的单调队列。

记录方案的话就开一个数组对应记一下就可以了。

3 注意事项

不遵守上述事项的结果就是我调了一天。

4 代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
// #define int long long
#define uint unsigned int
#define ull unsigned long long
#define N 310000
#define M 70
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,m,c,d,a[N],f[M][100000],sum[N],g[M][100000];
int q[N],l,r;

inline int get_posi(int id,int jd){
    return id*c+(jd-id);
}

inline void prework(){
    n++;
    for(int i=1;i<=n*c+m;i++) sum[i]=a[i]+sum[i-1];
}

inline int compeat(int id,int k){
    return f[id-1][k]-sum[get_posi(id-1,k)];
}

inline void print(int id,int jd){
    if(g[id][jd]<=0) return;
    print(id-1,g[id][jd]);
    int posi=get_posi(id-1,g[id][jd])-c+1;
    if(posi>0) printf("%d ",posi);
}

int main(){
    read(n);read(m);read(c);read(d);
    for(int i=1;i<=n*c+m;i++) read(a[i]);
    prework();
    for(int i=1;i<=n;i++){
        l=r=0;
        for(int j=0;j<=n+m&&j<=(d+1)*i;j++){
            while(l<r&&(q[l+1]<j-d-1||q[l+1]<i-1)) l++;
            if(j>=i&&l<r){
                int k=q[l+1];
                int now=get_posi(i,j),last=get_posi(i-1,k);
                f[i][j]=f[i-1][k]-sum[last]+sum[now-c+1];
                g[i][j]=k;
            }
            while(l<r&&compeat(i,q[r])<compeat(i,j)) r--;
            q[++r]=j;
        }
    }
    printf("%d\n",f[n][n+m]);
    print(n,n+m);
    return 0;
}