1079: PIPI的存钱罐

完全背包问题
但题目因为需要min，而我用-1来做标记，导致我得判断可不可行，无法压缩为一维dp数组，如果我用1e9做标记就可以了

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=510;
int w[N];
int val[N];
const int M=10010;
int dp[N][M];
int main(){while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){scanf("%d%d",&val[i],&w[i]);}for(int i=1;i<=m;i++){dp[0][i]=-1;          //-1代表impossible }for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){     //j=0的时候，肯定存钱罐为0元 if(j<w[i]){dp[i][j]=dp[i-1][j];}else{if(dp[i-1][j]!=-1&&dp[i][j-w[i]]!=-1){dp[i][j]=min(dp[i][j-w[i]]+val[i],dp[i-1][j]);}else if(dp[i-1][j]!=-1&&dp[i][j-w[i]]==-1){dp[i][j]=dp[i-1][j];}else if(dp[i-1][j]==-1&&dp[i][j-w[i]]!=-1){dp[i][j]=dp[i][j-w[i]]+val[i];}else dp[i][j]=-1;}
//				if(dp[i][j]!=-1){
//					cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
//				}}}if(dp[n][m]==-1){printf("impossible\n");}else{printf("%d\n",dp[n][m]);}}return 0;
}