题目

Description

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

Input

测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（<=30）是发票张数。随后是 N 行输入，每行的格式为：
m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。

Sample Input

200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0

Sample Output

123.50
1000.00
1200.50

题解

首先要判断发票是不是能报销：

• 总额不超过1000
• 单项不超过600
• 只有A、B、C三种物品

如果发票不能报销直接忽略掉就行
如果可以报销，就是01背包问题
套用算法即可

由于钱数带小数,因此应该将钱数×100化为整数

然而这道题最关键的地方应该是动态内存吧
题目里没有给具体的数据范围
在OJ上试了下,不是溢出就是超内存
没办法就用了new和delete

里面这部分不加上会报错~~(虽然我觉得不加貌似没问题)~~

dp = NULL;
while(dp == NULL)
    dp = new int[(int)(Q * 100) + 5];

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;




int *dp = NULL;

int v;

void ZeroOnePack(int cost,int weight) {
    for(int i = v; i >= cost; i--)
        dp[i] = max(dp[i],dp[i - cost] + weight);
}

bool Do() {
    double Q;
    int N;
    scanf("%lf%d",&Q,&N);
    if(N == 0)
        return false;

    v = (int)(Q * 100);

    if(!dp)
        delete[] dp;
    dp = NULL;

    while(dp == NULL)
        dp = new int[(int)(Q * 100) + 5];

    memset(dp,0,sizeof(int)*(int)(Q * 100) + 5);


    for(int i = 0;i < N;i++) {
        int m;
        scanf("%d",&m);
        double *money = new double[m + 5];
        double A,B,C,sum;
        A = B = C = sum = 0;
        for(int j = 0;j < m;j++) {
            char t;
            scanf("\n%c:%lf",&t,&money[j]);
            sum += money[j];
            if(t >= 'A'&&t <= 'C') {
                switch(t) {
                    case 'A':
                    A += money[j];
                    break;
                    case 'B':
                    B += money[j];
                    break;
                    case 'C':
                    C += money[j];
                    break;
                }
            } else {
                sum += 1001;
            }
        }
        if(A <= 600 && B <= 600 && C <= 600 && sum <= 1000)
            ZeroOnePack((int)(sum * 100),(int)(sum * 100));
    }
    printf("%.2f\n",(double)dp[v] / 100);
    return true;
}

int main() {
    while(Do());
    return 0;
}