自动搬运

查看原文

来自洛谷，原作者为

	淸梣ling 看，简单吧，谁也没有受伤的世界，达成了。

搬运于2025-08-24 22:20:23，当前版本为作者最后更新于2020-10-27 16:45:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

porblem

P6394

与摆花很相似。（其实就是摆花加强版）

大意：

有 $k$ 棵树，每棵树下有 $s_i$ 朵樱花，求收集樱花数量总和为 $n$ 的方案数。可以在任意一棵树下结束。

此题 $DP$ 与递推的思路其实是差不多的，严格来说还是个 $DP$ 题。详细思路可以看其他大佬题解。

细读题目，这不就是一道多重背包吗？此时我们将背包容量看成樱花数，那么 $f_{p}$ 为摘 $p$ 朵樱花的方案数，那么就可以直接做了。

for(i=1;i<=k;i++)//前i棵树
 for(p=n;p>=0;p--)//多重背包转换为01背包
  for(j=1;j<=min(s[i],p);j++)
   f[p]=(f[p]+f[p-j])%10086001;

然而此时看一眼数据 $1\le n,k\le5\times10^{3}$,显然多重背包 $O(kn^2)$ 的时间还是太耗时了，此时观察第三层循环， 每次的 $f_p$ 都是加上一个区间，所以可以直接用一个前缀和来计算，那么第三层循环就可以省掉了。

最后附上 $AC$ 代码，时间复杂度 $O(nk)$

#include<iostream>
#include<cstdio>
using namespace std;

const int M=10086001;
int f[5001];
long long s[5001];//前缀和
int num,ans;

int main()
{
	int n,t,i,j,p,k;
	cin>>n>>k;
	
	s[0]=f[0]=1;

	for(i=1;i<=k;i++)
	{
		cin>>t;
		
		for(j=1;j<=n;j++)//更新前缀和
		s[j]=s[j-1]+f[j];
		
		for(p=n;p>=0;p--)//多重背包
		f[p]=(f[p]+s[p-1]-s[p-min(t,p)-1])%M;//利用前缀和
		
		num+=t;//判断是否有解
		ans=(ans+f[n])%M;//累加第i棵树下收集n朵花的方案
		
	}
	
	if(num<n)
	cout<<"impossible";
	else
	cout<<ans;
	return 0;
}