自动搬运

查看原文

来自洛谷，原作者为

	天梦 知行合一，不负韶华，方可以一人独战天下!

搬运于2025-08-24 22:04:35，当前版本为作者最后更新于2021-06-29 17:31:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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 注意事项

• 在 dp 中，所有的变量的范围一定要卡死。
• 所有不合法的状态一定不要随意赋值。
• 不要随意的初始化。
• 所做的一切操作一定要符合你的状态。

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

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;
}