打卡信奥刷题（3090）用C++实现信奥题 P7132 小 L 的零食

P7132 小 L 的零食题目背景小 L 很喜欢吃零食。题目描述提交时自动开启 O2 优化。小 L 现在想把一些零食放在一个盒子里。但是零食没放稳就会摔坏所以小 L 希望求出有多少种稳定的堆放零食的方法。零食都可以抽象成一个1×11\times11×1的正方形而盒子的底部可以看成长度为nnn的一维线段。准确地说零食被分为nnn堆从左到右地放在盒子里面依次记为第1,2,…,n1,2,\ldots,n1,2,…,n堆。我们认为每一堆的高度hih_ihi​是这一堆零食的数量且任意一堆都可以不包含任何零食。我们定义第iii堆零食是稳定的当且仅当hi≤mh_i\le mhi​≤m即这一堆零食高度不超过mmm。在满足上一条的同时满足以下两条之一或同时满足i1i1i1或ininin此时有一侧是盒子内壁所以这一堆不会倒下max⁡{hi−1,hi1}≥hi−di\color{red}\max\{h_{i-1},h_{i1}\}\ge h_i-d_imax{hi−1​,hi1​}≥hi​−di​此时它两侧的两堆零食有一堆足够高可以支撑这一堆不倒下。我们定义一种稳定的堆放零食的方法是一个长度为nnn的hih_ihi​的序列满足按这个序列堆放出来的零食每一堆都是稳定的。显然盒子里最多放下n×mn\times mn×m个零食我们认为小 L 的零食数量不少于n×mn\times mn×m并且不必将所有零食全部放进盒子。额外地我们认为每一个零食都是完全一样的。输入格式总共包括222行。第一行包含两个正整数n,mn,mn,m。第二行包含nnn个整数d1,d2…,dnd_1,d_2\ldots,d_nd1​,d2​…,dn​意义如【题目描述】中红色部分所示。每行的两个数字间由单个空格隔开数据在 Windows 下生成。行末不保证没有多余空格。输出格式一行一个整数表示有多少种稳定的堆放零食的方法结果对998244353998244353998244353取模。输入输出样例 #1输入 #13 3 3 1 1输出 #159输入输出样例 #2输入 #210 13 12 13 1 4 5 9 7 0 3 8输出 #2851695394说明/提示本题采用如下计分策略subtask111#1∼1\sim{}1∼#88810%10\%10%n,m≤5n,m\le5n,m≤5subtask222#9∼9\sim{}9∼#12121230%30\%30%n,m≤5×102n,m\le5\times10^2n,m≤5×102subtask333#13∼13\sim{}13∼#16161620%20\%20%n,m≤3×103n,m\le3\times10^3n,m≤3×103subtask444#17∼17\sim{}17∼#24242440%40\%40%n,m≤7×103n,m\le7\times10^3n,m≤7×103。对于100%100\%100%的数据1≤n,m≤7×1031\le n,m\le7\times10^31≤n,m≤7×1030≤di≤m0\le d_i\le m0≤di​≤m。你必须通过一个 subtask 内所有测试点才被认为通过该 subtask。本题开启子任务依赖。C实现#includebits/stdc.husingnamespacestd;inlineintread(){ints0,w1;charchgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9)ss*10ch-0,chgetchar();returns*w;}intd[7003];longlongans[7003][2],pre[7003][2];constlonglongp998244353;signedmain(){intnread(),mread();for(inti1;in;i)d[i]read();for(inti0;im;i)pre[i][1]i1;for(inti2;in;i){for(intj0;jm;j)ans[j][1](pre[min(jd[i-1],m)][0](j-d[i]0?0:p-pre[j-d[i]-1][0])pre[m][1](j-d[i]0?0:p-pre[j-d[i]-1][1]))%p,ans[j][0](j-d[i]-10?0:(pre[j-d[i]-1][1]pre[j-d[i]-1][0])%p);pre[0][1]ans[0][1],pre[0][0]ans[0][0];for(intj1;jm;j)pre[j][1](pre[j-1][1]ans[j][1])%p,pre[j][0](pre[j-1][0]ans[j][0])%p;}printf(%lld\n,(pre[m][0]pre[m][1])%p);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容