题解 P6394 【樱花，还有你】
淸梣ling
2020-10-27 16:45:52
# porblem
[P6394](https://www.luogu.com.cn/problem/P6394)
与[摆花](https://www.luogu.com.cn/problem/P1077)很相似。~~（其实就是摆花加强版）~~
#### 大意：
有 $k$ 棵树，每棵树下有 $s_i$ 朵樱花，求收集樱花数量总和为 $n$ 的方案数。**可以在任意一棵树下结束**。
------------
此题 $DP$ 与递推的思路其实是差不多的，严格来说还是个 $DP$ 题。详细思路可以看其他大佬题解。
细读题目，这不就是一道多重背包吗？此时我们将背包容量看成樱花数，那么 $f_{p}$ 为摘 $p$ 朵樱花的方案数，~~那么就可以直接做了~~。
```cpp
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)$
```cpp
#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;
}
```