HDU - 1864 最大报销额（DP，01背包）_综合

HDU - 1864 最大报销额

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[3000010],w[40];//DP数组小于300W就会RE
int main()
{
    double x,y;int t,k;while(scanf("%lf%d",&x,&t)&&t){
    memset(dp,0,sizeof dp);memset(w,0,sizeof w);int sum=x*100;int l=0;while(t--){
    scanf("%d",&k);int a=0,b=0,c=0;char ch;int flag=1;while(k--){
    scanf(" %c:%lf",&ch,&y);int v=y*100;if(ch=='A'&&a+v<=60000) a+=v;else if(ch=='B'&&b+v<=60000) b+=v;else if(ch=='C'&&c+v<=60000) c+=v;else flag=0;}if(a+b+c<=100000&&a<=60000&&b<=60000&&c<=60000&&flag)w[++l]=a+b+c;}for(int i=1;i<=l;i++)for(int j=sum;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+w[i]);printf("%.2f\n",dp[sum]/100.0);}return 0;
}