Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贡献RE三次-，- 才发现算最极限的话，dp应该开10000以上。附代码。

Posted by Gentleh at 2012-12-25 23:57:27 on Problem 3211
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct node
{
int all,num;
int cost[105];
};

node sum[15];
char color[15][15];

int main()
{
int M,N;
while(scanf("%d%d",&M,&N)!=EOF)
{
if(M==0 && N==0)
break;
for(int i=1;i<=M;i++)
{
cin>>color[i];
sum[i].all=0;
sum[i].num=0;
for(int j=0;j<105;j++)
sum[i].cost[j]=0;
}
for(int i=1;i<=N;i++)
{
int value;
char temp[15];
cin>>value>>temp;
for(int j=1;j<=M;j++)
{
if(strcmp(temp,color[j])==0)
{
sum[j].all+=value;
sum[j].cost[sum[j].num]=value;
sum[j].num ++;
break;
}
}
}
int ans=0;
for(int i=1;i<=M;i++)
{
if(sum[i].all==0)
continue;
int tsum=sum[i].all/2;
int dp[10005]={0};
for(int j=0;j<sum[i].num;j++)
{
for(int k=tsum;k>=sum[i].cost[j];k--)
dp[k]=max(dp[k],dp[k-sum[i].cost[j]]+sum[i].cost[j]);
}
ans += (sum[i].all-dp[tsum]);
}
printf("%d\n",ans);
}
return 0;
}

```

Followed by: