题解 P4852 【yyf hates choukapai】

ouuan

2018-08-26 09:06:23

Solution

为了方便下文中设 $s=n*c+m$ ### 算法一(纯暴力) 暴力枚举所有方案。 时间复杂度:$O(C^{\,n}_{\;s})$,然而实际上有一堆剪枝,剪完之后复杂度会不会下一个数量级呢?出题人懒得算,反正数据这么小,暴力20分肯定稳的。 期望得分:$20$ 分 ### 算法二(d=m) 因为 $d=m$ ,可以不管 $d$ 的限制 设 $f(i,j)$ 表示前 $i$ 张卡中连抽 $j$ 次的最大欧气,则可以得到方程: $f(i,j)=\max(f(i-1,j)+a[i],f(i-c,j-1)+a[i-c+1])$ 两种转移分别代表第 $i$ 张卡是单抽/一次连抽的结尾。 输出方案:记录一下每个 $f(i,j)$ 是由谁转移来的,算完dp之后从 $n$ 倒回去,如果倒回去的过程中某两张卡的间隔是 $c$ 代表这两张卡之间有一次连抽 时间复杂度:$O(sn)$ 期望得分:$20$ 分 ### 算法三(无优化dp) 选一组牌 $[l,r]$ 连抽其实就是使欧气总和减少了 $\sum\limits_{i=l+1}^ra_i$ ,所以预处理出 $b_i=\sum\limits_{j=i+1}^{i+c-1}a_j\ (i∈[1,s-c+1])$ ,题目就变成了选择 $n$ 个 $b_i$ ,它们两两的下标之差大于等于 $c$ 且小于等于 $c+d$,求它们的和的最小值。特别地,选择的第一个 $b_i$ 下标要小于等于 $d+1$,最后一个 $b_i$ 下标要大于等于 $s-c-d+1$(不这样转化也能做,但出题人感觉转化之后方便一些) 设 $f(i,j)$ 为在 $b_{[1,i]}$ 中选择 $j$ 个且选择 $b_i$ 的最小和,可以得到: $f(i,j)=\min\limits_{k∈[i-c-d,i-c]}(f(k,j-1))+b[i]$ 时间复杂度:$O(snd)$ 期望得分:$50$ 分 ### 算法四(数据分治) ~~使用数据分治结合算法二和算法一/三,可以获得更高的分数。~~ 时间复杂度:$O(d==m?sn:C^{\,n}_{\;s}||snd)$ 期望得分:$40/70$ 分 ### 算法五(不会输出方案) ~~看出题人多么仁慈还给你准备了部分分~~ 时间复杂度:$O(?)$ 期望得分:$12$~$60$ 分 ### 算法六(单调队列优化dp) 看这玩意 → $k∈[i-c-d,i-c]$ 嗯用单调队列优化一下就好了 不会单调队列?[~~如果一个人比你小,还比你强,那你就永远打不过他了~~](https://sweetlemon.blog.luogu.org/dan-diao-dui-lie) 输出方案:记录一下每个 $f(i,j)$ 由谁转移而来,就说明选了这个 $b_i$ ,而选了某个 $b_i$ 就说明 $i$ 是某一次连抽的起始 时间复杂度:$O(sn)$ 期望得分:$100$ 分 ### Bonus ~~在~~[~~我用v4评测机的第一次提交的编译信息~~](https://www.luogu.org/record/show?rid=9924927)~~里可以看到出题人的良心提示:~~ ``` if (sta[i]<1||sta[i]>s-c+1||i>1&&(sta[i]-sta[i-1]<c||sta[i]-sta[i-1]>c+d)) ``` 从这一行可以看出两次连抽的起始下标之差要在 $[c,c+d]$ 内。 实际上是v4评测机神仙到能显示spj的warning...然而并不知道为什么之后的提交就没有这个waring了. ### 标程 ``` #include <iostream> using namespace std; const int N=45,M=80005,C=3005; const int S=N*C+M; int n,m,c,d,s,a[S],b[S],f[S][N],p[S][N],q[N][S][2],head[N],tail[N],sum,ans[N],anss,ansi; //其实可以只开一个单调队列,然而出题人懒 int main() { int i,j; cin>>n>>m>>c>>d; s=n*c+m; for (i=1;i<=s;++i) { cin>>a[i]; sum+=a[i]; } for (i=2;i<=c;++i) { b[1]+=a[i]; //先算出b1 } for (i=2;i<=s-c+1;++i) { b[i]=b[i-1]-a[i]+a[i+c-1]; //然后O(1)算出剩下的b } for (i=1;i<=n;++i) { head[i]=1; //将所有单调队列初始化为空队 } for (i=1;i<=s-c+1;++i) { if (i<=c) { f[i][1]=b[i]; //i<=c时之前必然没有连抽,只有f(i,1)有定义,而此时队列还是空的,所以直接赋为bi就好了 } else { for (j=(i+c-2)/(c+d)+1;j<=(i+c-1)/c&&j<=n;++j) //应该是f(i,j)有定义的准确范围,自己手推一下就可以推出来了,然而两个验题的都没有把范围卡死就过了 { if (head[j-1]<=tail[j-1]&&q[j-1][head[j-1]][1]<i-c-d) { ++head[j-1]; //将下标小于i-c-d的b出队 } if (j-1>=(i-2)/(c+d)+1&&j-1<=(i-1)/c) //如果f(i-c,j-1)有定义就将其入队 { while (head[j-1]<=tail[j-1]&&q[j-1][tail[j-1]][0]>=f[i-c][j-1]) { --tail[j-1]; } q[j-1][++tail[j-1]][0]=f[i-c][j-1]; q[j-1][tail[j-1]][1]=i-c; } f[i][j]=q[j-1][head[j-1]][0]+b[i]; p[i][j]=q[j-1][head[j-1]][1]; //记录f(i,j)由谁转移而来 if (i>=s-c+1-d&&j==n&&anss<sum-f[i][j]) //只有下标大于等于s-c+1-d的时候才能用f(i,n)更新答案 { anss=sum-f[i][j]; ansi=i; } } } } cout<<anss<<endl; for (j=n;j>=1;--j) { ans[j]=ansi; ansi=p[ansi][j]; } for (j=1;j<=n;++j) { cout<<ans[j]<<' '; } return 0; } ```