【题目来源】https://www.luogu.com.cn/problem/P1510【题目描述】精卫终于快把东海填平了只剩下了最后的一小片区域了。同时西山上的木石也已经不多了。精卫能把东海填平吗?事实上东海未填平的区域还需要至少体积为 v 的木石才可以填平而西山上的木石还剩下 n 块每块的体积和把它衔到东海需要的体力分别为 k 和 m。精卫已经填海填了这么长时间了她也很累了她还剩下的体力为 c。【输入格式】输入文件的第一行是三个整数vnc。从第二行到第 n1 行分别为每块木石的体积和把它衔到东海需要的体力。【输出格式】输出文件只有一行如果精卫能把东海填平则输出她把东海填平后剩下的最大的体力否则输出 Impossible不带引号。【输入样例一】100 2 1050 550 5【输出样例一】0【输入样例二】10 2 150 510 2【输出样例二】Impossible【数据范围】对于 20% 的数据0n≤50对于 50% 的数据0n≤1000对于 100% 的数据0n≤10^4所有读入的数均属于 [0,10^4]最后答案不大于 c。【算法分析】● 闫氏 DP 分析法https://www.bilibili.com/video/BV1X741127ZM● 最后一步法https://www.bilibili.com/video/BV1xb411e7ww【算法代码】f[j] 表示容量为 j 时能获得的最大价值。#include bits/stdc.h using namespace std; const int maxn1e5; int val[maxn],vol[maxn],f[maxn]; int v,n,c; int main() { cinvnc; for(int i1; in; i) cinval[i]vol[i]; for(int i1; in; i) { for(int jc; jvol[i]; j--) { f[j]max(f[j],f[j-vol[i]]val[i]); } } for(int i0; ic; i) { if(f[i]v) { coutc-i; return 0; } } coutImpossible; return 0; } /* in: 10 2 1 50 5 10 2 out: Impossible */【参考文献】https://www.cnblogs.com/Hoyoak/p/11373507.htmlhttps://www.acwing.com/file_system/file/content/whole/index/content/12355190/https://www.cnblogs.com/lipeiyi520/p/12293384.htmlhttps://blog.csdn.net/hnjzsyjyj/article/details/147405964