【题目来源】
【题目描述】
精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗?
事实上，东海未填平的区域还需要至少体积为 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 分析法：
● 最后一步法：
【算法代码】
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 2out:
Impossible
*/
【参考文献】