【动态规划背包前缀和滑动窗口】P6394 樱花，还有你|普及+-编程实验室

本文涉及知识点

C++动态规划
C++背包问题
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
C++算法：滑动窗口及双指针总结

樱花，还有你

题目背景

Dear Ling,
呐，你知道吗？听说樱花飘落的速度是秒速五厘米哦。
……所以，再等等吧！三月，武汉大学，樱花就快来了呢。
你一定会陪我一起看吧，在酥软的阳光下，我会悄悄牵起你的手，感受你熟悉的温度，糟糕，脸儿也不小心被粉嫩嫩的樱花映红的呢。
对了，一定记得带口罩！你那时还是有些虚弱吧。但天依会保护你的！
还有啊，樱花还可以做好多好多的点心呢！收集一些飘落樱花吧，我想喝樱花茶，还想吃樱饼，你一定要亲手给我做嗷！

题目描述

与题意有关的句子已加粗。

但别急，我们就这样彳亍而行吧，需不着停留或回头，前面不是还有k kk棵樱花树么？我算了算，你可要收集恰好n nn朵樱花。我还发现，在第i ii棵树下最多能收集到s i s_isi朵樱花（收集了0 00朵樱花也算收集了樱花）。

呐，考考你吧！你有多少种方案能够收集到恰好n nn朵樱花呢？

特殊地，如果你收集不到n nn朵樱花，请告诉我impossible。

注意：如果你早早地收集到了n nn朵樱花，你可以立刻告诉我，也可以陪我继续向前走，一直到第k kk棵樱花树下收集了樱花后就必须交差啦！期间你在任何一棵树收集完樱花后就告诉我，形成的方案都是不同的哦！

输入格式

第一行两个正整数n , k n,kn,k，表示要收集n nn朵樱花，而前方还有k kk棵樱花树。

接下来一行k kk个正整数s 1 , s 2 , ⋯ , s k s_1,s_2,\cdots,s_ks1,s2,⋯,sk，其中s i s_isi表示最多在第i ii棵樱花树下收集到s i s_isi朵樱花。

输出格式

一行一个整数，表示恰好收集到n nn朵樱花的方案数。

由于答案可能太大，请输出答案对10086001 1008600110086001取模后的值。

特殊地，如果收集不到n nn朵樱花，请输出一个字符串impossible。

样例 #1

样例输入 #1

3 4 1 1 1 1

样例输出 #1

样例 #2

样例输入 #2

10 9 9 6 8 7 9 6 5 4 3

样例输出 #2

样例 #3

样例输入 #3

10 5 2 2 2 2 1

样例输出 #3

impossible

提示

样例解释 #1

我们以下列方式表示一种方案：( a 1 , a 2 , ⋯ , a l e n ) (a_1,a_2,\cdots,a_{len})(a1,a2,⋯,alen)，其中∑ i = 1 l e n a i = n \sum_{i=1}^{len} a_i =n∑i=1lenai=n，l e n lenlen表示在第l e n lenlen棵樱花树下收集完樱花后就交差了，a i a_iai表示在第i ii棵树下收集了a i a_iai朵樱花。

那么有下列5 55种方案：( 1 , 1 , 1 ) (1,1,1)(1,1,1)，( 1 , 1 , 1 , 0 ) (1,1,1,0)(1,1,1,0)，( 0 , 1 , 1 , 1 ) (0,1,1,1)(0,1,1,1)，( 1 , 0 , 1 , 1 ) (1,0,1,1)(1,0,1,1)，( 1 , 1 , 0 , 1 ) (1,1,0,1)(1,1,0,1)。

样例解释 #3

最多能收集到9 99朵樱花，所以不能收集到10 1010朵樱花，输出impossible。

数据范围

本题采用捆绑测试。

Subtask 1（5 Points），∑ s i < n \sum s_i < n∑si<n。
Subtask 2（20 Points），n , k ≤ 20 n,k \leq 20n,k≤20。
Subtask 3（55 Points），n , k ≤ 5 × 10 2 n,k \leq 5\times 10^2n,k≤5×102。
Subtask 4（20 Points），n , k ≤ 5 × 10 3 n,k \leq 5\times 10^3n,k≤5×103。

对于100 % 100\%100%的数据，1 ≤ n , k ≤ 5 × 10 3 1 \leq n,k \leq 5\times 10^31≤n,k≤5×103，0 ≤ s i ≤ n 0 \leq s_i \leq n0≤si≤n。

题目背景 ( 续 )

何等聪明的你一定会站在某棵树下，捧着n nn朵可爱的樱花，像孩子似的向我邀功吧。
那就别怪我成全你哦，我会轻跳起来，环住你的脖子，揭起你的口罩，尝一尝你的嘴唇。
你会不会说，“像樱花一样甜”呢？
反正，我的脸一定已经像樱花一样红了吧。
……
当你看到这封信，别哭呀……
冬天从这座城市夺走的，春天会补偿我们的。
待你好了，陪我去看樱花，可好？

Yours,
Yi

动态规划(背包问题)+ 前缀和(滑动窗口)

动态规划的状态表示

dp[i][j] 对前i棵樱花树收集了樱花，总共收集了j朵樱花。i∈ \in∈[0,k],j∈ \in∈[0,n]

动态规划的转移方程

枚举后续状态
dp[i][j] =∑ \sum∑dp[i-1][max(0,j-s_{i-1})…j]

动态规划的填表顺序

i = 1 to k j =0 to n

动态规划的初始值

dp[0][0]=1，其它dp[0]为0。

动态规划的返回值

∑ \sum∑dp[i].back()

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<bitset>usingnamespacestd;template<classT1,classT2>std::istream&operator>>(std::istream&in,pair<T1,T2>&pr){in>>pr.first>>pr.second;returnin;}template<classT1,classT2,classT3>std::istream&operator>>(std::istream&in,tuple<T1,T2,T3>&t){in>>get<0>(t)>>get<1>(t)>>get<2>(t);returnin;}template<classT1,classT2,classT3,classT4>std::istream&operator>>(std::istream&in,tuple<T1,T2,T3,T4>&t){in>>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);returnin;}template<classT=int>vector<T>Read(){intn;scanf("%d",&n);vector<T>ret(n);for(inti=0;i<n;i++){cin>>ret[i];}returnret;}template<classT=int>vector<T>Read(intn){vector<T>ret(n);for(inti=0;i<n;i++){cin>>ret[i];}returnret;}template<intMOD=1000000007>classC1097Int{public:C1097Int(longlongllData=0):m_iData(llData%MOD){}C1097Intoperator+(constC1097Int&o)const{returnC1097Int(((longlong)m_iData+o.m_iData)%MOD);}C1097Int&operator+=(constC1097Int&o){m_iData=((longlong)m_iData+o.m_iData)%MOD;return*this;}C1097Int&operator-=(constC1097Int&o){m_iData=(m_iData+MOD-o.m_iData)%MOD;return*this;}C1097Intoperator-(constC1097Int&o){returnC1097Int((m_iData+MOD-o.m_iData)%MOD);}C1097Intoperator*(constC1097Int&o)const{return((longlong)m_iData*o.m_iData)%MOD;}C1097Int&operator*=(constC1097Int&o){m_iData=((longlong)m_iData*o.m_iData)%MOD;return*this;}C1097Intoperator/(constC1097Int&o)const{return*this*o.PowNegative1();}C1097Int&operator/=(constC1097Int&o){*this/=o.PowNegative1();return*this;}booloperator==(constC1097Int&o)const{returnm_iData==o.m_iData;}booloperator<(constC1097Int&o)const{returnm_iData<o.m_iData;}C1097Intpow(longlongn)const{C1097Int iRet=1,iCur=*this;while(n){if(n&1){iRet*=iCur;}iCur*=iCur;n>>=1;}returniRet;}C1097IntPowNegative1()const{returnpow(MOD-2);}intToInt()const{return(m_iData+MOD)%MOD;}private:intm_iData=0;;};classSolution{typedefC1097Int<10086001>BI;public:intAns(constintN,vector<int>&s){constintK=s.size();if(accumulate(s.begin(),s.end(),0LL)<=N){return-1;}vector<BI>pre(N+1);pre[0]=1;BI ans;for(inti=1;i<=K;i++){vector<BI>preSum={0};for(constauto&p:pre){preSum.emplace_back(preSum.back()+p);}vector<BI>cur(N+1);for(intj=0;j<=N;j++){intpinx=max(0,j-s[i-1]);cur[j]+=preSum[j+1]-preSum[pinx];}ans+=cur.back();pre.swap(cur);}returnans.ToInt();}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGintn,k;cin>>n>>k;autos=Read<int>(k);#ifdef_DEBUG/*printf("N=%d", n); Out(s, ",s=");*///Out(b, ",b=");#endifautores=Solution().Ans(n,s);if(res<0){cout<<"impossible";}else{cout<<res;}return0;}

单元测试

intN;vector<int>s;TEST_METHOD(TestMethod11){N=3,s={1,1,1,1};autores=Solution().Ans(N,s);AssertEx(5,res);}TEST_METHOD(TestMethod12){N=10,s={9,6,8,7,9,6,5,4,3};autores=Solution().Ans(N,s);AssertEx(68345,res);}TEST_METHOD(TestMethod13){N=10,s={2,2,2,2,1};autores=Solution().Ans(N,s);AssertEx(-1,res);}

扩展阅读

算法为骨，CAD为魂
亲士工具箱：支持中望CAD2024、AutoCad2013及以上，多年承接CAD项目的精华
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019C++17
或者操作系统：win10 开发环境： VS2022C++17
如无特殊说明，本算法用**C++**实现。

【动态规划背包前缀和滑动窗口】P6394 樱花，还有你|普及+