蓝桥杯备赛-精卫填海-DP

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？
事实上，东海未填平的区域还需要至少体积为 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≤104，所有读入的数均属于 [0,104]，最后答案不大于 c。

//精卫填海,8/10,2个超内存
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int main(){int v, n, c;cin >> v >> n >> c;//需要的体积，石头的数量，目前的体力值int k[100000];//体积int m[100000];//体力//或//vector<int> k(n + 1); // 体积//vector<int> m(n + 1); // 体力for (int i = 1; i <= n; i++){cin >> k[i] >> m[i];}vector<vector<int>> a(n + 1,vector<int>(v+1,0));//用i个石头填满j体积，需要的最少体力//必要：初始化一个很大的数表示不可能，用零块填满是不可能的，所有初始化最大。下面条件判断用的是min，如果不初始化最大，那么后面一直都是for (int i = 0; i < v + 1; i++)a[0][i] = 100000;//不必要：a[i][0]是0或100000不影响结果/*for (int i = 0; i < n + 1; i++)a[i][0] = 100000;*/for (int i = 1; i <= n; i++) {for (int j = 1; j <= v; j++) {//动态规划的核心：保持j的不变if (k[i]>=j) //一个石头就能填满{a[i][j] = min(a[i - 1][j], m[i]);//不放、只放一个、全放（舍）}else //一个石头填不满{a[i][j] = min(a[i - 1][j - k[i]]+m[i], a[i - 1][j]);//放、不放}}}if (a[n][v]>c)cout << "Impossible";elsecout << c-a[n][v];//注意用c-，不要忘记了return 0;
}