题解 P4852 yyf hates choukapai

· · 题解

一道毒瘤的dp

状态难设计，转移较简单。

设计状态及方程

题意其实很好理解，抽卡，找运气最大值，dp应该稳的。

然后看题，关键信息有几个:

  1. 不能连续单抽 d 次 ，这意味着我们的状态必须记录或推导到开始单抽的时刻。

  2. 有连抽和单抽的次数限制，必须记录连抽或单抽的次数。

但是这边我们有了很多种选择，蒟蒻本人连续想假了三个状态QAQ。

最终确定 dp 数组只需记下用过的连抽数和考虑到第几位数即可。

即， dp[i][j] 表示用第 j 次连抽恰好走到第 i 位的最大欧气值。

不过这个状态好像不如标程好转移，不过这是蒟蒻能想通并写出方程的较好理解的状态了。

然后考虑到恰好用了 j 步走到第 i 位，那么后面的状态不可能对这个状态再产生任何影响。所以写出初步的转移方程：

注：（sum是前缀和数组）。 ### 单调队列优化 毕竟标签上明明白白地写着单调队列嘛。 那么看回上面的暴力方程式，我们发现几个特性： 1. $sum[i-c+1]$ 与 $k$ 无关，可以从括号内提出来。 2. $dp[k][j-1]$ 与 $sum[k]$ 都仅与 $k$ 相关。 3. 条件 $i-c\leq d$ 可以转化为 $i\leq c+d$ ，即当 $c\leq k$ 时 $i$ 必须满足 $i>c+d$ 。 容易判断出状态： 1. 当 $c\leq k$ 时 $k \in [max(c+d,i-c-d),i-c]$ 。 2. 当 $c>k$ 时 $k \in [i-c-d,i-c]$ 。 那么讨论到这里我们已经很容易发现，我们可以用单调队列对于每一个 $j$ 维护条件下的 $dp[k][j-1]-sum[k]$ 的最大值即可。 ### 输出答案 根据 $dp$ 数组的定义，很容易发现答案就在恰好用完第 $n$ 次连抽所达到的点里面找，不过注意要统计最后的散点。 $ans=\max_{i=n*c}^{n*c+m}\{dp[i][n]+sum[n*c+m]-sum[i-1]\}

找方案应该是没啥问题的，就是记下每个状态是从哪里转移的，然后打个指针过去，然后从后面递推回去输出即可。

代码

#include<bits/stdc++.h>
#define rep(a,b,c) for(register int c=(a);c<=(b);++c)
using namespace std;
const int N=2e5+5,INF=-0x3f3f3f3f,M=45;
inline int read()
{
    int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
    while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
int dp[N][M],sum[N],nxt[N][M],c,d;
struct DEQ{int val,num;}deq[N];inline void To(DEQ &k,int x,int y){k.val=x;k.num=y;}int h,t;
inline void print(int cur,int i){if(!i)return; print(nxt[cur][i],i-1);printf("%d ",cur-c+1);}
int main()
{
    int n=read(),m=read();c=read(),d=read();
    int len=n*c+m;rep(1,len,i)sum[i]=sum[i-1]+read();
    memset(dp,-0x3f,sizeof(dp));rep(1,d,i)dp[i][0]=sum[i];dp[0][0]=0;
    rep(1,n,j){h=1;t=0;rep(c,len,i)if(i-c*j<=m)
    {
        while(h<=t&&deq[h].num<((i>c+d&&c+1>i-c-d)?c+1:i-c-d))h++;
        while(h<=t&&deq[t].val<=(dp[i-c][j-1]-sum[i-c]))t--;To(deq[++t],dp[i-c][j-1]-sum[i-c],i-c);
        dp[i][j]=deq[h].val+sum[i-c+1];nxt[i][j]=deq[h].num;
    }}
    int ans=0,mx=0;rep(len-d,len,i)if(dp[i][n]+sum[len]-sum[i]>ans)mx=i,ans=dp[i][n]+sum[len]-sum[i];
    printf("%d\n",ans);print(mx,n);return 0;
}

码风较丑仅供对拍（滑稽）。