本文涉及知识点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样例输入 #13 4 1 1 1 1样例输出 #15样例 #2样例输入 #210 9 9 6 8 7 9 6 5 4 3样例输出 #268345样例 #3样例输入 #310 5 2 2 2 2 1样例输出 #3impossible提示样例解释 #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_{i1}^{len} a_i n∑i1len​ai​nl 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 15 Points∑ s i n \sum s_i n∑si​n。Subtask 220 Pointsn , k ≤ 20 n,k \leq 20n,k≤20。Subtask 355 Pointsn , k ≤ 5 × 10 2 n,k \leq 5\times 10^2n,k≤5×102。Subtask 420 Pointsn , 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×1030 ≤ 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()代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateintMOD1000000007classC1097Int{public:C1097Int(longlongllData0):m_iData(llData%MOD){}C1097Intoperator(constC1097Into)const{returnC1097Int(((longlong)m_iDatao.m_iData)%MOD);}C1097Intoperator(constC1097Into){m_iData((longlong)m_iDatao.m_iData)%MOD;return*this;}C1097Intoperator-(constC1097Into){m_iData(m_iDataMOD-o.m_iData)%MOD;return*this;}C1097Intoperator-(constC1097Into){returnC1097Int((m_iDataMOD-o.m_iData)%MOD);}C1097Intoperator*(constC1097Into)const{return((longlong)m_iData*o.m_iData)%MOD;}C1097Intoperator*(constC1097Into){m_iData((longlong)m_iData*o.m_iData)%MOD;return*this;}C1097Intoperator/(constC1097Into)const{return*this*o.PowNegative1();}C1097Intoperator/(constC1097Into){*this/o.PowNegative1();return*this;}booloperator(constC1097Into)const{returnm_iDatao.m_iData;}booloperator(constC1097Into)const{returnm_iDatao.m_iData;}C1097Intpow(longlongn)const{C1097Int iRet1,iCur*this;while(n){if(n1){iRet*iCur;}iCur*iCur;n1;}returniRet;}C1097IntPowNegative1()const{returnpow(MOD-2);}intToInt()const{return(m_iDataMOD)%MOD;}private:intm_iData0;;};classSolution{typedefC1097Int10086001BI;public:intAns(constintN,vectorints){constintKs.size();if(accumulate(s.begin(),s.end(),0LL)N){return-1;}vectorBIpre(N1);pre[0]1;BI ans;for(inti1;iK;i){vectorBIpreSum{0};for(constautop:pre){preSum.emplace_back(preSum.back()p);}vectorBIcur(N1);for(intj0;jN;j){intpinxmax(0,j-s[i-1]);cur[j]preSum[j1]-preSum[pinx];}anscur.back();pre.swap(cur);}returnans.ToInt();}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGintn,k;cinnk;autosReadint(k);#ifdef_DEBUG/*printf(N%d, n); Out(s, ,s);*///Out(b, ,b);#endifautoresSolution().Ans(n,s);if(res0){coutimpossible;}else{coutres;}return0;}单元测试intN;vectorints;TEST_METHOD(TestMethod11){N3,s{1,1,1,1};autoresSolution().Ans(N,s);AssertEx(5,res);}TEST_METHOD(TestMethod12){N10,s{9,6,8,7,9,6,5,4,3};autoresSolution().Ans(N,s);AssertEx(68345,res);}TEST_METHOD(TestMethod13){N10,s{2,2,2,2,1};autoresSolution().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 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。