HDU 2546 饭卡(01背包+预处理)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int dp[MAXN];
int c[MAXN];
int n,m;
int main()
{
  while(~scanf("%d",&n)){
    if(n==0) break;
    for(int i=0;i<n;i++){
      scanf("%d",&c[i]);
    }
    sort(c,c+n);              // 这里排一下序，因为要用5块钱去买最贵的，所以把最贵的放在后面方便点
    memset(dp,0,sizeof(dp));
    scanf("%d",&m);
    if(m<5){cout<<m<<endl;}   // 当钱少于5的时候直接输出
    else{
      for(int i=0;i<n-1;i++){              // 遍历n-1次，把最贵的跳过
        for(int j=m-5;j>=c[i];j--){        // 钱数应该-5
          dp[j] = max(dp[j],dp[j-c[i]]+c[i]);
        }
      }
      printf("%d\n",m - c[n-1] - dp[m-5]);    // m是总钱数，c[n-1]是最贵的菜，dp[m-5]是当前最贵的状态
    }
  }
  return 0;
}
/*
   [来源] HDU 2546
   [题目] 饭卡
   [大意]
      有一张饭卡，买饭的之前需要判断一下是不是大于5，小于5的话就不能买了，直接输出这个钱数就好了，大于5的
      话，先排一下序，然后按01背包写就好，具体过程看代码注释吧。
  [输入]
     1
     50
     5
     10
     1 2 3 2 1 1 2 3 2 1
     50
     0
  [输出]
    -45
    32
*/