题解 P4852 【yyf hates choukapai】
ouuan
2018-08-26 09:06:23
为了方便下文中设 $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;
}
```