自动搬运

查看原文

来自洛谷，原作者为

	H17 *　*

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

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

以下是正文

和这篇题解有些类似，但是讲的更加详细，并且有参考与这篇题解。

题目分析

这是一道 DP 题目，一开始想到区间 DP，但是发现胶太难处理了，而且没法转移，于是换方法。

不久我发现了无论如何两边胶带不可能少于 $a,b$ 于是可以通过把胶、长度当状态作 DP。

设 $f_{i,j,k}$ 为前后分别有 $i,j$ 个胶，总长度为 $k$ 的胶带数。

捣鼓半天没搞出来，而且空间不符合限制。考虑优化状态，鉴于前后都有胶带，而且前后性质相同（即都可以一起处理）。想想为什么？

于是设 $f_{i,j}$ 表示总长度为 $i$ 前或者后有 $j$ 个胶的数量（另一边没有胶，可以随便折）。

由于转移过程比较难推导（个人认为），所以在下一板块【转移】。

转移

首先我们可以枚举折的长度，从而进行展开操作。折的长度至少是 $j$。

此时 $f_{i,j}=f_{i-j,j}$，然而可以折的更长，为了找到普遍规律，我们设折的长度为 $j+k$。

于是得到 $f_{i,j}=\sum\limits_{k=0}^{(i-2\times j)\div 2}f_{i-j-k,j+k}$，显然转移的时间不够优秀。

根据之前转移的依据得出：我们转移的变化量 $k$ 纯属是根据 $j$ 而限定范围的（提示是 $f_{i,j+1}$，读者可以想一想为什么，再继续阅读）。

我们发现 $f_{i,j+1}=\sum_{k=1}^{(i-2\times j)\div 2}f_{i-j-k,j+k}$，原因是 $k=0$ 时就成了折 $j$ 段胶，然而这时必须是 $j+1$ 段胶。

鉴于这两个式子差距很小，我们可以用 $f_{i,j+1}$ 来得到 $f_{i,j}$。

转移方程 $f_{i,j}=f_{i,j+1}+f_{i-j,j}$，前一项如上所述，后一项则是差的折 $j$ 段胶的情况。

统计答案

由于我们的 DP 只考虑了一边，另一边答案一样。我们考虑找到一个分割点（非胶），左边和右边分别折，求总数。

注意到左边必须是严格折到 $i$ 而非前 $i$ 段（想一想为什么），后面可以。这样可以避免重复。

答案是 $\sum\limits_{i=a}^{n-b}(f_{i,a}-f_{i-1,a})\times f_{n-i,b}$。

这里解释为什么要严格折到 $i$，如果是前 $i$ 段，那么前 $i-1$ 段的值已经被统计了，这样会重复。然而后半边不会重复。

初始状态

$f_{i,i}=1,f_{i,i+x}=0(x>0)$ 原因是全是胶没法折，胶到后边去（范围外）就乱套了，不能算。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1001,mod=10301;
int n,a,b,f[N][N],ans;
int main(){
	cin>>n>>a>>b;
	for(int i=0;i<=n;i++)
		f[i][i]=1;
	for(int i=0;i<=n;i++)
		for(int j=i-1;j>=0;j--)
			f[i][j]=f[i][j+1]+f[i-j][j],f[i][j]%=mod;
	for(int i=a;i<=n-b;i++)
		ans+=(f[i][a]-f[i-1][a])*f[n-i][b]%mod,ans=(ans+mod)%mod;//注意答案可能出现负数
	cout<<ans;
	return 0;
}