HDU1864 最大报销额 DP

http://acm.hdu.edu.cn/showproblem.php?pid=1864

这一题的题义真的让人很伤神啊。其中不超过600元，是指某一类物品的总和不超过600元，1000元是指整张发票的钱不超过1000元，对于浮点数，我们将其统一乘以100。

该题背包的体积就是发票数，对于第 i 张发票，其最大报销额就是 dp[i] = Max[ ( dp[j]+Fee[i] )  <= LIMIT], 其中dp[j]可达（满足在1～i-1张发票之前能够报销j张发票，其总和为不超过额定最大报销额的最大值）。

代码如下：

#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

int M, N, Fee[35], cnt, dp[35], fe2[5];
const int smax = 60000, tmax = 100000;

inline int max(int x, int y)
{
    return x < y ? y : x;
}

int getdata(int &fee)
{
    int cnt2, cc, flag = 0;
    char ss;
    double c;
    scanf("%d", &cnt2, &ss);
    for (int i = 1; i <= cnt2; ++i) {
        scanf(" %c:%lf", &ss, &c);
        cc = (int)(c*100);
        fee += cc;
        if (fee > tmax) {
            flag = 1;
            continue;
        }
        if (ss-'A'>=0 && ss-'A'<=2) {
            fe2[ss-'A'] += cc;
            if (fe2[ss-'A'] > smax) {
                flag = 1;
            }
        }
        else {
            flag = 1;
        }
    }
    return flag ? 0 : 1;
}

void zero_one(int x)
{
    for (int i = cnt; i > 0; --i) {
        if (dp[i-1] != -1 && dp[i-1]+Fee[x] <= M) {
            dp[i] = max(dp[i], dp[i-1]+Fee[x]);
        }
    }
}

void DP()
{
    for (int i = 0; i < cnt; ++i) {  // 对cnt张发票进行01背包
        zero_one(i);
    }
}

int main()
{
    int leage, fee, Max;
    double c;
    while (scanf("%lf %d", &c, &N), N) {
        Max = 0;
        memset(dp, 0xff, sizeof (dp)); 
        dp[0] = 0;
        cnt = 0;
        M = (int)(c*100);
        for (int i = 0; i < N; ++i) {
            fee = 0;
            fe2[0] = fe2[1] = fe2[2] = 0;
            if (getdata(fee)) {  // 判定该发票是否合法
                Fee[cnt++] = fee;
            }
        }
        DP();
        for (int i = cnt; i >= 0; --i) {
            if (dp[i] != -1 && dp[i] <= M) {
                Max = Max > dp[i] ? Max : dp[i];
            }
        }
        printf("%.2lf\n", Max * 0.01);
    }
    return 0;
}