NYOJ 311 完全背包(恰好装满)

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX(a,b) a>b?a:b
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000005;
int dp[MAXN];
int w[MAXN];
int val[MAXN];
int n,m,p;
int main()
{
  scanf("%d",&n);
  while(n--){
    scanf("%d%d",&m,&p);
    for(int i=0;i<m;i++){
      scanf("%d%d",&w[i],&val[i]);
    }
    memset(dp,-INF,sizeof(dp));
    dp[0] = 0;
    for(int i=0;i<m;i++){
      for(int j=w[i];j<=p;j++){
        dp[j]=MAX(dp[j],dp[j-w[i]]+val[i]);    // 尽量用宏定义或者三目运算符吧
      }
    }
    if(dp[m]<0){
      printf("NO\n");
    }
    else{
      printf("%d\n",dp[p]);
    }
  }
  return 0;
}
/*
  [来源] NYOJ 311
  [题目] 完全背包
  [大意]
     顾题目思义，就是一道完全背包问题，但是要判断是否恰好装满，详细可以看Piggy-Bank这个题解。唯一比较坑的是交了快十次，
     一直TLE，最后发现直接调用max比较函数会慢。
  [输入]
     2
     1 5
     2 2
     2 5
     2 2
     5 1
   [输出]
     NO
     1
*/