精卫填海 题解

水题，但我交了三次才过。。。
原因：不优化到一维数组会RE
定义$DP[c]$为体力为$c$时可获得的最大体积
最后遍历查找$DP$数组，如果没有体积大于$V$的就是无解，否则输出最小值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct A{int k,m;}a[10005];//石块结构体,k为体积,m为体力 
int V,n,C;//至少V体积填平,n个石块,剩余C体力 
int DP[10005];//前i个物品且体力为C时所填的最大体积 
int maxn(int x,int y){
	if(x>y){return x;}
	return y;
}
int main(){
	cin>>V>>n>>C;
	for(int i=1;i<=n;i++) cin>>a[i].k>>a[i].m;
	for(int i=1;i<=n;i++){
		for(int c=C;c>=a[i].m;c--){
			DP[c]=maxn(DP[c],DP[c-a[i].m]+a[i].k);
		}
	}
	for(int i=1;i<=C;i++){
		if(DP[i]>=V){
			cout<<C-i;return 0;
		}
	} 
	cout<<"Impossible";
	return 0;
}