题解 P6394 【樱花，还有你】

· · 题解

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