HDU 1864 最大报销额 (DP-01背包问题)
最大 HDU 01 DP 背包 问题
2023-09-11 14:17:19 时间
题意:中文题,你懂得。
析:拿过题目一看,本来以为是贪心,仔细一看不是贪心,其实是一个简单的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; }
相关文章
- 【Luogu2711】小行星(网络流,最大流)
- 【HDU 2063】过山车(二分图最大匹配模板题)
- Java 集合List、Set、HashMap操作三(查找List中的最大最小值、遍历HashTable、List元素替换、List查找位置)
- HDU 5402 Travelling Salesman Problem (模拟 有规律)(左上角到右下角路径权值最大,输出路径)
- HDU 2504 又见GCD (最大公因数+暴力)
- 剑指 Offer 47. 礼物的最大价值
- 【HDU 5855】Less Time, More profit(网络流、最小割、最大权闭合子图)
- Kakao拟16亿美元收购韩国最大音乐流媒体服务
- HDU 1532||POJ1273:Drainage Ditches(最大流)
- O(1)时间复杂度实现入栈、出栈、获得栈中最小元素、获得栈中最大元素(转)
- hdu 2444 The Accomodation of Students (判断二分图,最大匹配)
- 晶科电力打造山东省最大物流港分布式光伏项目
- 英特尔今年年中将裁掉1.2万名员工:十年内规模最大
- [LeetCode] 1191. K-Concatenation Maximum Sum K次串联后最大子数组之和
- [LintCode] Maximal Square 最大正方形
- [LintCode] Maximum Gap 求最大间距
- 习题5.4 找出4*5矩阵中值最小和最大元素,并分别输出其值及所在的行号和列号。