1. 题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1864
2. 简要分析：这道题看起来不难，求最大报销额。想法是先找到符合要求的发票，然后求符合要求的发票的最大报销金额。
但是，这道题的陷阱好几个，一不注意就WrongAnswer。我就是一上午快Wrong成狗了。。。
易错点：
（1）可以报销的物品只有A、B、C类，其他类物品不可报销。
（2）是单类物品不能超过600元，不是单项，如A:310 A:320，那A类物品为630元，不符合要求，不能报销；
（3）进行动态规划前要对数组进行由大到小排序，不然特殊测试数据没法通过。如：
1000.00 4
1 A:300.00
1 B:300.00
1 A:200.00
1 C:500.00 该测试样例的正确结果应该为1000.00，原题目给的数据太弱了，难以发现错误。
3. 解题代码：
//HOJ--1864:最大报销额 0MS / 284K
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
float value;
}ticket[35];
int cmp(float a,float b)
{
return a > b;
}
int main()
{
int i,j,N,n; //N:发票张数 n:每张发票上物品数
int CanUse[35]; //判断单张发票是否符合要求
char kind,ch; //kind:物品的种类
float sum,val; //sum:总报销值 val:每件物品的价值
float sum_A,sum_B,sum_C; //单类物品的总金额
while(cin>>sum>>N && N)
{
for(i=0;i<N;i++)
{
CanUse[i]=1;
ticket[i].value=0;
cin>>n;//输入每张发票上物品件数
sum_A=sum_B=sum_C=0.00;
for(j=0;j<n;j++)
{
cin>>kind>>ch>>val;
if(kind!='A' && kind!='B' && kind!='C')//注意：只有A，B,C三类可以报销
CanUse[i]=0;
else
{
if(kind=='A') sum_A=sum_A+val;
else if(kind=='B') sum_B=sum_B+val;
else if(kind=='C') sum_C=sum_C+val;
}
ticket[i].value=ticket[i].value+val;
}
if(sum_A>600.00 || sum_B>600.00 || sum_C>600.00)//每张发票上单类物品价值不可超过600
CanUse[i]=0;
if(ticket[i].value>1000.00 || ticket[i].value>sum)//每张发票价值不可超过1000元 且每张发票总金额不可超过总报销额
CanUse[i]=0;
}
float t[35];
int len=0;
for(i=0;i<N;i++)
{
if(CanUse[i])
{
t[len]=ticket[i].value;
len++;
}
}
sort(t,t+len,cmp);//排序函数一定要有，不然上述提到的测试数据会出错！
//这里最大钱数应该要用动态规划来求，dp[n]=max(dp[n-1]+t[n],t[n]),限制条件为各值都要小于总报销值sum
float dp[35];//动态规划数组
dp[0]=t[0];
for(i=1;i<len;i++)
{
if(dp[i-1]+t[i]>=t[i])
{
if(dp[i-1]+t[i]<=sum)
dp[i]=dp[i-1]+t[i];
else dp[i]=max(dp[i-1],t[i]);//这里也很关键！
}
else
{
dp[i]=ticket[i].value;//ticket[i].value>sum CanUse[i]=0保证了单张发票总额不会超过sum
}
}
//找出dp[]中的最大值
float max_value=0.00;
for(i=0;i<len;i++)
{
if(dp[i]>max_value)
max_value=dp[i];
}
printf("%.2lf\n",max_value);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163026.html
