HDU 1864.最大报销额

320


题目



Description  


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


Input  


测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N,其中 Q 是给定的报销额度,N(<=30)是发票张数。随后是 N 行输入,每行的格式为:
m Type1:price1 Type2:price2 ... Typem:pricem
其中正整数 m 是这张发票上所开物品的件数,Typei 和 pricei 是第 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上试了下,不是溢出就是超内存
没办法就用了newdelete

里面这部分不加上会报错~~(虽然我觉得不加貌似没问题)~~
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论