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

       这是一道01背包问题，但是需要预处理一下，因为当你的钱不够5块钱的时候，你什么都买不了，所以直接输出钱数，当你的钱大于5块钱的时候，你可以先拿出来5块钱，留着最后去买最贵的菜，现在你剩下m-5块钱，排个序把最贵的留在最后,然后就用01背包把这m-5尽量装满(遍历1~n-1种菜，因为n是最贵的菜要留给最后)，然后再用那剩下的5块钱去买最贵的菜，最后就是最优解m-dp[m-5]-dp[n]。我写的代码是从0开始的，所以最后的解是m-dp[m-5]-dp[n-1]，理解就好。。

AC代码：

#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
*/