大体题意：有n件衣服，m种颜色，某人和他的女炮一起洗衣服，必须一种颜色洗完，才能洗另一种颜色，每件衣服都有时间，那个人洗都一样，问最少用时。
poj万恶的C++和G++,害得我CE了三次
/* 背包啊……竟然有这么多玩法 不知道是不是被树形DP搞晕了，一上来就设了个三维数组，“f[i][j][0]代表前i件衣服， 时间差为j，且男生洗得多的时间”。搞了两个小时发现思路错了，这样会使两个背包毫无差别， 答案一定是错的。 正解：对于每种颜色，做一个01背包求方案树，加入j这个体积能填出来，那么另一个背包体积是 sum-j，那么ans=min(ans,max(j,sum-j)) */ #include<cstdio> #include<iostream> #include<cstring> #include<map> #include<vector> #define N 110 #define M 100010 #define INF 10000010 using namespace std; int f[M],num[N],sum[N],w[N][N],n,m; map<string,int> color; void init() { for(int i=1;i<=n;i++) { string s; cin>>s; color[s]=i; } for(int i=1;i<=m;i++) { int t;string s; scanf("%d",&t);cin>>s; int c=color[s]; num[c]++; w[c][num[c]]=t; sum[c]+=t; } int tot=0; for(int T=1;T<=n;T++) { if(!num[T])continue; memset(f,0,sizeof(f)); int ans=INF; f[0]=1; for(int i=1;i<=num[T];i++) for(int j=sum[T];j>=w[T][i];j--) f[j]+=f[j-w[T][i]]; for(int i=0;i<=sum[T];i++) if(f[i])ans=min(max(i,sum[T]-i),ans); tot+=ans; } printf("%d ",tot); } int main() { while(~scanf("%d%d",&n,&m)) { memset(num,0,sizeof(num)); memset(sum,0,sizeof(sum)); memset(w,0,sizeof(w)); memset(f,0,sizeof(f)); if(n==0&&m==0)break; init(); } return 0; }