C++信息竞赛进级第6讲 资源分配.pptx

学科竞赛编程教研研究院C++NOIPNOIIOI

题目描述能量项链

输入输出格式输入格式：第一行是一个正整数N(4≤N≤100)，表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记(1≤i≤N)，当iN时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出格式：一个正整数 ，为一个最优聚合顺序所释放的总能量。

输入输出样例

1PARTONE#includebits/stdc++.husingnamespacestd;intn,e[300],s[300][300],maxn=-1;intmain(){cinn;for(inti=1;i=n;i++){cine[i];e[i+n]=e[i];}//珠子由环拆分为链，重复存储一遍for(inti=2;i2*n;i++){for(intj=i-1;i-jnj=1;j--){//从i开始向前推for(intk=j;ki;k++)//k是项链的左右区间的划分点s[j][i]=max(s[j][i],s[j][k]+s[k+1][i]+e[j]*e[k+1]*e[i+1]);//状态转移方程：max(原来能量，左区间能量+右区间能量+合并后生成能量）if(s[j][i]maxn)maxn=s[j][i];//求最大值}}coutmaxn;return0;}

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NN元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1?5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。金明的预算方案

输入格式：第11行，为两个正整数，用一个空格隔开：Nm（其中N(32000)表示总钱数，m(60)为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j?1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v10000），p表示该物品的重要度（1?5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q0，表示该物品为附件，q是所属主件的编号）输出格式：一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。输入输出格式

输入输出样例

PARTONEvoidread(){inti,j,a,b,c,num=0;//num计主件的个数intmap[61]={0};cinnm;//读入总钱数和m件物品n=n/10;//每件物品都是10的整数倍，可以优化程序for(i=1;i=m;i++){cinabc;//先用变量保存--判断好是主还是附近再赋值if(c==0)//先填主件，c才是主件{num++;//！！计一共有多少个主件，附件都记在主件第二维下标[1][2]v[num][0]=a/10;p[num][0]=b;//i=4，是第4件其实不是的-因为前面的有可能是附件，而附件不记数map[i]=num;//记下第i个物品的主件序号continue;}//c是物品的序号是i，不是num，而本题所有的附件要放在num主件上c=map[c];//i=2,c=1时c=map[1]=1,i=3时，c=1,c=map[1]=1//i=4,map[4]=2,i=5,map[5]=3if(v[c][1]==0)//如果第c件物品的第1个附件还没有{v[c][1]=a/10;p[c][1]=b;continue;}else{v[c][2]=a/10;p