HDU 1864 最大报销额 (DP-01背包问题)

题意：中文题，你懂得。

析：拿过题目一看，本来以为是贪心，仔细一看不是贪心，其实是一个简单的01背包问题（DP），不过这个题的坑是在处理发票上，刚开始WA了一次。

分析一下什么样的发票是不符合要求的：

1.某一种物品的和超过了600元，注意一定是和，因为有的物品出数据时故意分开了，这是一个坑。

2.发票中含有除ABC这三类的发票是不符合的。

3.发票中总额超过了1000元也是不符合的。

只要处理好上面这三点，AC就小意思了。剩下的就是一个01背包，相当于让你求最大的价值。

有点小技巧，因为是浮点数，我们可以把它们都扩大100倍，最后再缩小，可以减少误差。（这个是借鉴网上的）

代码如下：

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int a[35];

int d[30*1000*100+10];

int main(){

    double q;

    int n, m, s;

    while(scanf("%lf", &q)){

        s = (int)(q * 100);

        scanf("%d", &n);  if(!n)  break;

        char ch;

        int indx = 0, x;

        while(n--){

            int alla = 0, allb = 0, allc = 0;

            bool ok = true;

            int sum1 = 0;

            scanf("%d", &m);

            for(int i = 0; i < m; ++i){

                scanf(" %c:%lf", &ch, &q);

                x = (int)(q*100);

                if(ch < 'A' || ch > 'C')  ok = false;

                if('A' == ch)  alla += x;

                else if('B' == ch)  allb += x;

                else if('C' == ch)  allc += x;

                if(x > 60000) ok = false;

                sum1 += x;

            }

            if(alla > 60000 || allb > 60000 || allc > 60000 || sum1 > 100000)  ok = false;

            if(ok)  a[indx++] = sum1;

        }

        memset(d, 0, sizeof(d));

        for(int i = 0; i < indx; ++i)

            for(int j = s; j >= a[i]; --j)

                d[j] = max(d[j], d[j-a[i]]+a[i]);

        printf("%.2lf\n", (double)d[s]/100.0);

    }

    return 0;

}

巴特西

HDU 1864 最大报销额 (DP-01背包问题)

最新文章

热门文章