【题目来源】
https://www.luogu.com.cn/problem/P1510
【题目描述】
精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗?
事实上，东海未填平的区域还需要至少体积为 v 的木石才可以填平，而西山上的木石还剩下 n 块，每块的体积和把它衔到东海需要的体力分别为 k 和 m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为 c。
【输入格式】
输入文件的第一行是三个整数：v，n，c。
从第二行到第 n+1 行分别为每块木石的体积和把它衔到东海需要的体力。
【输出格式】
输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出 Impossible（不带引号）。
【输入样例一】
100 2 10
50 5
50 5
【输出样例一】
0
【输入样例二】
10 2 1
50 5
10 2
【输出样例二】
Impossible
【数据范围】
对于 20% 的数据，0<n≤50；
对于 50% 的数据，0<n≤1000；
对于 100% 的数据，0<n≤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 maxn=1e+5; int val[maxn],vol[maxn],f[maxn]; int v,n,c; int main() { cin>>v>>n>>c; for(int i=1; i<=n; i++) cin>>val[i]>>vol[i]; for(int i=1; i<=n; i++) { for(int j=c; j>=vol[i]; j--) { f[j]=max(f[j],f[j-vol[i]]+val[i]); } } for(int i=0; i<=c; i++) { if(f[i]>=v) { cout<<c-i; return 0; } } cout<<"Impossible"; return 0; } /* in: 10 2 1 50 5 10 2 out: Impossible */
【参考文献】
https://www.cnblogs.com/Hoyoak/p/11373507.html
https://www.acwing.com/file_system/file/content/whole/index/content/12355190/
https://www.cnblogs.com/lipeiyi520/p/12293384.html
https://blog.csdn.net/hnjzsyjyj/article/details/147405964
