题解：P17317 [KismetOI 2026 I] 作弊
lailai0916
·
·
题解
题意简述
部分比赛的 perf 尚未确定。对每种完整序列，可以将若干个互不相邻的位置替换为 D。求能得到的最大 rating，并计算所有完整序列的答案之和。
解题思路
先固定一个完整序列。若 n>k，替换位置 i 会使总和增加 D-p_i。所有被替换的位置不能相邻，所以最大增量是路径上的最大权独立集。
设 A_i 表示只考虑后缀 [i,n] 时的最大增量，则：
A_i=\max(A_{i+1},A_{i+2}+D-p_i)
$$
z_i=\max(0,D-p_i-z_{i+1})
$$
因此 $0\leq z_i\leq D+V\leq2V$。又因为 $A_{n+1}=0$，差分求和得到 $A_1=\sum_{i=1}^nz_i$。最优修改后的总和就是 $\sum_{i=1}^n(p_i+z_i)$。
rating 的另一部分是前 $k$ 项的最大前缀和。令 $h_i$ 表示从 $i$ 开始且终点不超过 $k$ 的最大非负前缀和。边界为 $h_{k+1}=0$，转移为：
$$
h_i=\max(0,p_i+h_{i+1})
$$
最终的 `maxp` 等于 $h_1$。$h_i$ 与 $z_i$ 都从右向左转移，因而可以放进同一个计数 DP。
先处理后缀 $[k+1,n]$，此时还不需要记录 $h$。设 $c_z$ 表示当前差分为 $z$ 的方案数，$s_z$ 表示这些方案中已处理部分的 $\sum(p_i+z_i)$ 之和。枚举当前位置的 perf 为 $x$，记 $z'=\max(0,D-x-z)$，转移为：
$$
\begin{aligned}
c'_{z'} & \gets c'_{z'}+c_z \\
s'_{z'} & \gets s'_{z'}+s_z+c_z(x+z')
\end{aligned}
$$
若 $p_i$ 已知，只执行一次转移。若 $p_i$ 未知，可以把 $x\in[-V,V]$ 分成两段聚合计算。
当 $x>D-z$ 时，$z'=0$。这段的方案数与 $x$ 之和都能通过等差数列公式一次加入。
当 $x\leq D-z$ 时，$z'=D-z-x$，并且 $x+z'=D-z$。不同的 $x$ 与一段连续的 $z'$ 一一对应，可以用差分数组区间加。因此，后缀的每个位置只需 $O(V)$ 时间。
再处理前 $k$ 个位置。状态增加最大前缀和这一维，分别维护方案数 $c_{h,z}$ 与总和 $s_{h,z}$。由于 $k,V\leq30$，这里可以枚举每个未知位置的全部可能值。对给定的 $x$ 同时计算：
$$
\begin{aligned}
h' & =\max(0,h+x) \\
z' & =\max(0,D-x-z)
\end{aligned}
$$
总和同时增加 $x+z'$。处理完位置 $1$ 后，每个完整序列落入唯一状态，答案为：
$$
\sum_{h=0}^{kV}\sum_{z=0}^{D+V}g_hs_{h,z}
$$
若 $n\leq k$，题目规定替换不会生效。此时只需统计 $h_i=\max(0,p_i+h_{i+1})$ 的方案数，最后计算 $\sum_hg_hc_h$。
每次转移都覆盖当前位置允许的全部 perf 值，且各取值互不重叠。因此，每个完整序列恰好被计算一次。$z$ 的递推由路径最大权独立集等价变形而来，$h_1$ 也正是所需最大前缀和。状态中累计的总和乘 $g_h$ 后，就是该序列的最优 rating。
时间复杂度为 $O(nV+k^2V^3)$，空间复杂度为 $O(kV^2)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100005;
const int M=905;
const int W=65;
const int mod=1000000007;
const int unk=-7912;
int p[N],g[M];
int cnt[W],sm[W],dc[W],ds[W];
int f[2][M][W],s[2][M][W];
int c[2][M];
int n,k,d,v,lim;
void add(int &x,ll y)
{
x=(int)((x+y)%mod);
if(x<0)x+=mod;
}
void upd(int l,int r,int x,int y)
{
if(l>r)return;
add(dc[l],x);
add(ds[l],y);
if(r<lim)
{
add(dc[r+1],-x);
add(ds[r+1],-y);
}
}
int calc1()
{
int cur=0;
c[cur][0]=1;
for(int i=n;i>=1;i--)
{
int nxt=cur^1;
memset(c[nxt],0,sizeof c[nxt]);
int l=p[i]==unk?-v:p[i],r=p[i]==unk?v:p[i];
for(int j=0;j<=(n-i)*v;j++)
{
int x=l;
while(x<=r)
{
add(c[nxt][max(j+x,0)],c[cur][j]);
x++;
}
}
cur=nxt;
}
int ans=0;
for(int i=0;i<=n*v;i++)add(ans,(ll)g[i]*c[cur][i]);
return ans;
}
void point(int j,int x)
{
int y=max(d-x-j,0);
upd(y,y,cnt[j],(int)((sm[j]+(ll)cnt[j]*(x+y))%mod));
}
int calc2()
{
cnt[0]=1;
for(int i=n;i>k;i--)
{
memset(dc,0,sizeof dc);
memset(ds,0,sizeof ds);
for(int j=0;j<=lim;j++)
{
if(cnt[j]==0&&sm[j]==0)continue;
if(p[i]!=unk)
{
point(j,p[i]);
continue;
}
int l=max(d-j+1,-v),r=v;
if(l<=r)
{
int len=r-l+1;
ll val=(ll)sm[j]*len+(ll)cnt[j]*(l+r)*len/2;
upd(0,0,(int)((ll)cnt[j]*len%mod),(int)(val%mod));
}
l=-v;
r=min(d-j,v);
if(l<=r)
{
int ql=d-j-r,qr=d-j-l;
upd(ql,qr,cnt[j],(int)((sm[j]+(ll)cnt[j]*(d-j))%mod));
}
}
for(int j=0;j<=lim;j++)
{
if(j)
{
add(dc[j],dc[j-1]);
add(ds[j],ds[j-1]);
}
cnt[j]=dc[j];
sm[j]=ds[j];
}
}
for(int j=0;j<=lim;j++)
{
f[0][0][j]=cnt[j];
s[0][0][j]=sm[j];
}
int cur=0;
int pos=k;
while(pos)
{
int nxt=cur^1;
memset(f[nxt],0,sizeof f[nxt]);
memset(s[nxt],0,sizeof s[nxt]);
int l=p[pos]==unk?-v:p[pos],r=p[pos]==unk?v:p[pos];
for(int i=0;i<=(k-pos)*v;i++)
{
for(int j=0;j<=lim;j++)
{
if(f[cur][i][j]==0&&s[cur][i][j]==0)continue;
int x=l;
while(x<=r)
{
int y=max(d-x-j,0),h=max(i+x,0);
add(f[nxt][h][y],f[cur][i][j]);
add(s[nxt][h][y],s[cur][i][j]+(ll)f[cur][i][j]*(x+y));
x++;
}
}
}
cur=nxt;
pos--;
}
int ans=0;
for(int i=0;i<=k*v;i++)
{
for(int j=0;j<=lim;j++)add(ans,(ll)g[i]*s[cur][i][j]);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>k>>d>>v;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=0;i<=k*v;i++)cin>>g[i];
lim=d+v;
cout<<(n<=k?calc1():calc2())<<'\n';
return 0;
}
```