自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:26:21，当前版本为作者最后更新于2020-11-13 14:23:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

DP。

设 $f_{i,j,k,l}$ 表示做第 $i$ 个烤肉串，用了 $j$ 秒，做了 $k$ 次梦，离可以做梦还有 $l$ 秒的方案数。

转移方程（注意 $t=0$ 的情况）：

时间复杂度 $O(nq^2t)$，不能通过。

注意到 $k\leq\left\lceil\dfrac{q}{t+1}\right\rceil$，缩小枚举上界，时间复杂度优化到 $O(nq^2)$。

前两维可以滚掉，空间复杂度 $O(qt)$。

为了减少边界特判，代码中的 $k$ 表示做了 $k-1$ 次梦。

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
int f[259][109];
int main(){
	int n,m,t,q,x,i,j,k,l;
	scanf("%d%d",&n,&t),f[1][0]=1;
	for(i=1;i<=n;++i){
		scanf("%d%d",&q,&x),m=min(q-x+1,q/(t+1)+2);
		for(j=1;j<=q;++j){
			for(k=m;k;--k){
				if(t)f[k][0]=(f[k][1]+f[k][0])%P;
				else f[k][0]=(f[k][0]+f[k-1][0])%P;
				for(l=1;l<t;++l)f[k][l]=f[k][l+1];
				if(t)f[k][t]=f[k-1][0];
			}
		}
		for(k=2;k<=m;++k)for(l=0;l<=t;++l)f[1][l]=(f[1][l]+f[k][l])%P,f[k][l]=0;
	}
	for(x=l=0;l<=t;++l)x=(x+f[1][l])%P;
	printf("%d",x);
	return 0;
}