题目P1510 精卫填海题目描述本题为改编题。发鸠之山其上多柘木。有鸟焉其状如乌文首白喙赤足名曰精卫其名自詨。是炎帝之少女名曰女娃。女娃游于东海溺而不返故为精卫。常衔西山之木石以堙于东海。——《山海经》精卫终于快把东海填平了只剩下了最后的一小片区域了。同时西山上的木石也已经不多了。精卫能把东海填平吗事实上东海未填平的区域还需要至少体积为v vv的木石才可以填平而西山上的木石还剩下n nn块每块的体积和把它衔到东海需要的体力分别为k kk和m mm。精卫已经填海填了这么长时间了她也很累了她还剩下的体力为c cc。输入格式输入文件的第一行是三个整数v , n , c v,n,cv,n,c。从第二行到第n 1 n1n1行分别为每块木石的体积和把它衔到东海需要的体力。输出格式输出文件只有一行如果精卫能把东海填平则输出她把东海填平后剩下的最大的体力否则输出Impossible。输入输出样例 #1输入 #1100 2 10 50 5 50 5输出 #10输入输出样例 #2输入 #210 2 1 50 5 10 2输出 #2Impossible说明/提示数据范围及约定对于20 % 20\%20%的数据0 n ≤ 50 0n \le 500n≤50对于50 % 50\%50%的数据0 n ≤ 1000 0n \le 10000n≤1000对于100 % 100\%100%的数据0 n ≤ 10 4 0n \le 10^40n≤104所有读入的数均属于[ 0 , 10 4 ] [0,10^4][0,104]最后答案不大于c cc。思路本来的思路是二维费用求最小体积但是内存会超限直觉可以用二维但没有清晰实现思路看了题解体力作为体积山石体积作为价值求不超过体力的最大山石体积。然后从前往后扫一遍数组当值超过所需值时输出剩余体力否则输出Impossible。代码#includebits/stdc.husingnamespacestd;constintM1e410;intn,V1,V2,v1,v2,f[M];//V1山石体积V2体力boolflag;intmain(){cinV1nV2;for(inti1;in;i){cinv1v2;for(intjV2;jv2;j--)f[j]max(f[j],f[j-v2]v1);}for(intj0;jV2;j)if(f[j]V1){coutV2-j;flagtrue;break;}if(!flag)puts(Impossible);return0;}结果