Washing Clothes（poj 3211）

大体题意：有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=;i<=n;i++)

    {

        string s;

        cin>>s;

        color[s]=i;

    }

    for(int i=;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=;

    for(int T=;T<=n;T++)

    {

        if(!num[T])continue;

        memset(f,,sizeof(f));

        int ans=INF;

        f[]=;

        for(int i=;i<=num[T];i++)

          for(int j=sum[T];j>=w[T][i];j--)

            f[j]+=f[j-w[T][i]];

        for(int i=;i<=sum[T];i++)

          if(f[i])ans=min(max(i,sum[T]-i),ans);

        tot+=ans;

    }

    printf("%d\n",tot);

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        memset(num,,sizeof(num));

        memset(sum,,sizeof(sum));

        memset(w,,sizeof(w));

        memset(f,,sizeof(f));

        if(n==&&m==)break;

        init();

    }

    return ;

}