学步园

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

这里有让人犯迷糊的地方，可能是题意不清楚。当满足下面条件之一的，这张发票就不能报销，相当于作废：

1.一张发票上有除了 'A' 'B' C"之外还有别的类型的消费

2.这张发票的总总消费大于1000

3.单项物品的价值超过600

这样就变成了01背包问题。即某张发票被报销和不被报销两种情况。

还有就是给定的总额和发票的消费总额都是两位小数，可以先给他们同时扩大100倍，最后输出的时候再缩小100倍。

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

const int maxn = 3000010;
int dp[maxn];

int chk(char ch)
{
	if(ch == 'A' || ch == 'B' || ch == 'C')
		return 1;
	return 0;
}

int main()
{
	double Q;
	int n,m,v;
	int a[40];
	while(~scanf("%lf %d",&Q,&n))
	{
		if(n == 0) break;
		v = Q*100;		//指定报销额扩大100倍
		for(int i = 1; i <= n; i++)
		{
			scanf("%d",&m);
			double A = 0,B = 0,C = 0,x,s = 0;
			int f = 1;
			char str;
			while(m--)
			{
				scanf(" %c:%lf",&str,&x);
				if(chk(str) == 0) f = 0;
				if(str == 'A') A += x;
				if(str == 'B') B += x;
				if(str == 'C') C += x;
				s += x;
			}
			if(A > 600 || B > 600 || C > 600 || s > 1000 || f == 0)
				a[i] = 0;	//该发票不符合要求，置为0.
			else a[i] = s*100;//否则发票的总价值也扩大100倍
		}
		
		memset(dp,0,sizeof(dp));
		dp[0] = 1;	//初始化。0肯定能达到
		int ans = 0;
		for(int i = 1; i <= n; i++)
		{
			for(int j = v; j >= a[i]; j--)
			{
				if(dp[j-a[i]])
				{
					dp[j] = 1;
					ans = max(ans,j);
				}
			}
		}
		printf("%.2lf\n",ans/100.0);	//最后还原
	}
	return 0;
}