P4852 yyf hates choukapai
风羽跃
·
·
题解
来波比较短的单调队列~
首先当前连抽多少次、单抽多少次、抽了多少牌这三个状态，我们只需要记录其二，就可以算出剩下那个。
由于连抽的次数上限只有40，因此我们先记一维连抽。
其次单抽和总牌数，显然记录总牌数更方便转移（好像也没方便多少），因此第二维我们记总牌数。
综上所述，我们用 f[i][j] 表示前 i 张牌连抽 j 次的最大欧气值。
考虑枚举本次连抽的位置 k(为了计算方便，我们设 k 为本次连抽的起始卡牌的前一个位置），转移方程显然：
其中 $\max(0,i-c-d) \le k \le i-c$。
题目还要求输出方案，开个数组记录前驱就好啦。
时间复杂度 $O(n^3)$。
先贴个暴力代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 200005
#define maxm 42
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int n,p,q,c,d,a[maxn],s[maxn],f[maxn][maxm],pre[maxn][maxm];
inline void print(int i,int j)
{
if(!j) return ;
print(pre[i][j],j-1);
cout<<pre[i][j]+1<<" ";
}
int main()
{
cin>>p>>q>>c>>d;
n=p*c+q;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
memset(f,0xcf,sizeof(f));
for(int i=1;i<=d;i++){
f[i][0]=s[i];
}
for(int j=1;j<=p;j++){
//注意外层循环先枚举j（其实枚举i或j都能写，但为了后续优化这里我们先枚举j）
for(int i=j*c;i<=n;i++){
for(int k=max(0,i-c-d);k<=i-c;k++){
if(f[k][j-1]+a[k+1]+s[i]-s[k+c]>f[i][j]){
f[i][j]=f[k][j-1]+a[k+1]+s[i]-s[k+c];
pre[i][j]=k;
}
}
}
}
cout<<f[n][p]<<endl;
print(n,p);
puts("");
return 0;
}
```
考虑优化，观察 $k$ 的取值范围，当 $i$ 增大时显然 $k$ 决策区间的左右边界都单调递增，所以用单调队列维护砍掉一维。
复杂度 $O(n^2)$。
AC 代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 200005
#define maxm 42
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int n,p,Q,c,d,a[maxn],s[maxn],f[maxn][maxm],pre[maxn][maxm];
int q[maxn],l=1,r=0;
inline void print(int i,int j)
{
if(!j) return ;
print(pre[i][j],j-1);
cout<<pre[i][j]+1<<" ";
}
inline int calc(int j,int k)
{
return f[k][j-1]+a[k+1]-s[k+c];
}
int main()
{
cin>>p>>Q>>c>>d;
n=p*c+Q;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
memset(f,0xcf,sizeof(f));
for(int i=1;i<=d;i++){
f[i][0]=s[i];
}
for(int j=1;j<=p;j++){
l=1,r=0;
for(int k=max(0,j*c-c-d);k<=j*c-c;k++){
while(l<=r&&calc(j,q[r])<=calc(j,k)) r--;
q[++r]=k;
}
for(int i=j*c;i<=n;i++){
while(l<=r&&q[l]<max(0,i-c-d)) l++;//弹掉左边失效的
if(l<=r) f[i][j]=calc(j,q[l])+s[i],pre[i][j]=q[l];//更新答案
int k=i+1-c;//下一个i的决策集合新元素
while(l<=r&&calc(j,q[r])<=calc(j,k)) r--;
q[++r]=k;
}
}
cout<<f[n][p]<<endl;
print(n,p);
puts("");
return 0;
}
```
最后补充一句：队列建议手写，常数小取用元素也方便。