HDU-1864-最大报销额

时间:2022-08-14 20:58:31

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1864

这题开始题意没搞清楚,就做题了,导致浪费了很多的时间,不应该啊,

注意事项:每张发票上,单项物品的价值不得超过600元,这里要小心,就是说    2  A:450  A:200  这张票是不能报销的  它为650了,

开始我没想到他会有这样的数据,这次还犯了一个低级错误,dp竟然没有初始化,这样的错误不能犯啊!

还有对于小数的处理我是直接乘以100的, 不知哪位高人有更好的办法,还请多多指点,

代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int dp[3000005];

int main(void)
{
int i,j,k;
double q,s,s1,s2,s3;
int n,m;
char c;
double p;
int v[35];
while(scanf("%lf%d",&q,&n)==2&&n)
{
k=0;
memset(dp,0,sizeof(dp));
int q1=q*100;
for(i=0;i<n;i++)
{
int ok=0;
s=0; s1=0; s2=0; s3=0;
scanf("%d",&m);
for(j=0;j<m;j++)
{
getchar();
scanf("%c:%lf",&c,&p);
if(c=='A')
{
s1=s1+p;
}
else if(c=='B')
{
s2=s2+p;
}
else if(c=='C')
{
s3=s3+p;
}
else
{
ok=1;
break;
}
}
s=s1+s2+s3;
if(s1<=600&&s2<=600&&s3<=600&&s<=1000&&ok==0)
{
v[k++]=s*100;
}
}
for(i=0;i<k;i++)
{
for(j=q1;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
}
}
printf("%.2lf\n",(double)dp[q1]/100);
}
return 0;
}

参数
234MS 12100K 1397 B