题解 P7132 【小 L 的零食】
Alex_Wei
·
·
题解
题目传送门。
题意简述：给定 n,m,d_{1,2,\cdots,n}，求有多少种序列 h_{1,2,\cdots,n} 满足 0\leq h_i\leq m 且对于所有 i\in[2,n-1] 有 \max(h_{i-1},h_{i+1})+d_i\ge h_i。
首先，看到 n,m\leq 7\times 10^3 考虑能否 \mathcal{O}(nm) DP。
考虑第 i 堆零食时，第 i+1 堆零食的高度会影响方案的可行性（即有后效性），所以不能单纯设 f_{i,j} 表示 h_i=j 的合法方案数。
不难想到按照 第 i 堆零食是否靠到了第 i-1 堆零食上（即 h_{i-1}+d_i 与 h_i 的关系） 将 h_i=j 时的合法方案数分成两类情况讨论：设 f_{i,j} 表示 h_i=j 且 h_{i-1}+d_i\geq h_i（即第 i 堆零食靠到了第 i-1 堆零食上，此时不关心 h_{i+1} 的大小）的合法方案数，g_{i,j} 表示 h_i=j 且 h_{i-1}+d_i<h_i 的合法方案数。
接下来推转移方程：记 l=\max(0,j-d_i),r=\min(m,j+d_{i-1})
。
$$f_{i,j}\gets f_{i,j}+\sum_{k=l}^m f_{i-1,k}$$
。$g_{i-1,k}\to f_{i,j}$：此时应满足 $k+d_i\geq j$ 且 $j+d_{i-1}\geq k$，即 $l\leq k\leq r$，即
$$f_{i,j}\gets f_{i,j}+\sum_{k=l}^r g_{i-1,k}$$
。综上，$f_{i,j}$ 的转移方程为：
$$f_{i,j}=\sum_{k=l}^m f_{i-1,k}+\sum_{k=l}^r g_{i-1,k}$$
。根据上面的思路，不难推出 $g_{i,j}$ 的转移方程：
$$g_{i,j}=\sum_{k=0}^{l-1}f_{i-1,k}+g_{i-1,k}$$
。补充说明：当 $g_{i-1,k}\to g_{i,j}$ 时，$k$ 应同时满足 $k\leq r$ 且 $k<l$，又因为 $d_i$ 的非负性有 $l\leq r$，所以此时 $k\leq l$。
由于最后一堆零食没有高度限制，所以最终答案为 $\sum f_{n,i}+g_{n,i}$。
最后前缀和优化 + 滚动数组优化即可，时间复杂度 $\mathcal{O}(nm)$。参考代码：
```cpp
const int N=7e3+5;
ll n,m,d[N],f[2][N],g[2][N];
int main(){
cin>>n>>m; for(int i=1;i<=n;i++)cin>>d[i];
for(int i=0;i<=m;i++)f[1][i]=i+1;
for(int i=2;i<=n;i++){
int p=i&1,q=p^1;
for(int j=0;j<=m;j++){
int l=max(0ll,j-d[i]),r=min(m,j+d[i-1]);
f[p][j]=(f[q][m]+g[q][r]-(l?f[q][l-1]+g[q][l-1]:0)+(j?f[p][j-1]:0)+mod)%mod;
g[p][j]=((l?f[q][l-1]+g[q][l-1]:0)+(j?g[p][j-1]:0))%mod;
}
} cout<<(f[n&1][m]+g[n&1][m])%mod<<endl;
return 0;
}
```