题解 P7132 【小 L 的零食】
Alex_Wei
2020-12-20 12:18:36
[题目传送门](https://www.luogu.com.cn/problem/P7132)。
> 题意简述：给定 $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-1,k}\to f_{i,j}$：此时应满足 $k+d_{i}\geq j$，但因为 $f$ 的定义，**不需要满足** $j+d_{i-1}\geq k$，所以此时 $k$ 的限制为 $\max(0,j-d_i)\leq k\leq m$，即
$$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;
}
```