自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:26:56，当前版本为作者最后更新于2020-12-20 12:18:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门。

题意简述：给定 $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)$。参考代码：

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;
}