P4852 yyf hates choukapai
zhendelan
·
·
题解
P4852 yyf hates choukapai
前置知识：wqs二分+单调队列优化dp。
分析
很容易看出，单抽是一个比连抽更优的操作。所以如果没有m的限制，那肯定是会一直用单抽的。
设答案为f(x)，x为单抽的次数。那么f(x)的图像肯定是一个上凸包(单抽的价值会不断下降,不要误以为单调上升的就一定是凸函数)。
这个时候函数的极值点(x,f(x))不一定会在题目m的范围限制内。我们要让他左移取极值点。
设f'(x)=f(x)-px，当p增大的时候，那么肯定极值点会往左移，所以当他刚好取在m点时，我们就找到了f(m)。然后我们二分这个p就可以了。
其实上面讲的比较复杂，讲人话就是给每次单抽一个额外费用，带着这个费用dp就会限制单抽的次数，然后使得单抽次数在限制范围内。当刚好只取到m次的时候，就是最优的。
那带着费用的时候怎么dp呢。
像其他题解一样写成单调队列优化就可以了。
设f[i]为前i个最多抽多少欧气值。
f[i]=\max_{i-j<=d}\{g[j]+(s[i]-s[j])+(i-j)*x,f[i-c]+a[i-c+1]\}
其中s为前缀和,a为每张卡的欧气值，g是为了限制次数产生的，为第i次连抽完后的最大值。
要注意边dp边记录单抽的次数。
时间复杂度
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,c,d;
const int N = 2e5+20;
int a[N],s[N];
double f[N],fq[N];
int cnt[N],from[N],q[N],tot,cntq[N],from1[N];
const double eps = 1e-2;
const double inf = 1e14;
int ans[N];
void solve(double extra)
{
f[0] = fq[1] = cntq[1] = q[1] = 0;
for(int i=1,h=1,t=1;i<=tot;i++)
{
f[i] = -inf;
if(i-c>=0&&f[i-c]+a[i-c+1]>f[i])
{
f[i]=f[i-c]+a[i-c+1],from[i] = i-c,cnt[i]=cnt[i-c];
while(h<=t && f[i]-s[i]+extra*i>fq[t])t--;
q[++t] = i;fq[t] = f[i]-s[i]+extra*i;cntq[t] = cnt[i];
from1[i] = from[i];
}
while(h<=t&&i-q[h]>d)h++;
if(h<=t&&fq[h]+s[i]-extra*i>f[i])
f[i]=fq[h]+s[i]-extra*i,from[i] = -q[h]-1,cnt[i] = cntq[h]+i-q[h];
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&c,&d);
tot = c*n+m;
for(int i=1;i<=tot;i++)
scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
double l = 0,r=1e4;
while(l+eps<r)
{
double mid = (l+r)/2;
solve(mid);
if(cnt[tot]>m) l=mid;
else r = mid;
}
solve(r);
int sum = 0,cntt=0,flag=0;
for(int i=tot;i;)
{
if(flag) from[i] = from1[i];
if(from[i]>=0) sum+=a[from[i]+1],ans[++cntt]=from[i]+1,i = from[i],flag=0;
else
{
from[i]++;
for(int j=-from[i]+1;j<=i;j++)sum+=a[j];
i=-from[i];
flag = 1;
}
}
printf("%d\n",sum);
for(int i=cntt;i;i--)printf("%d ",ans[i]);
return 0;
}
```