POJ Washing Clothes 洗衣服 （01背包，微变型）

题意：有多种颜色的衣服，由两个人合作来洗，必须洗完一种颜色才能洗下一种，求需要多少时间能洗完。

思路：将衣服按颜色分类，对每种颜色进行01背包，容量上限是该种颜色衣服全部洗完的耗时长一半，其实就是在最公平地平分工作量。因为一个先洗完就得等到另一人洗完。最后把洗完每种颜色的时长加起来返回。注:poj不允许用map，不然更省事，根据string和int做个哈希映射。

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 int m, n, big[], dp[];

 vector< vector<int> >   vect;

 char s[][], str[];

 int cal()

 {

     int ans=;

     for(int i=,sum=; i<=m; i++) //每种颜色

     {

         if(vect[i].empty()) continue;

         memset(dp,,sizeof(dp));

         for(int k=; k<vect[i].size(); k++) //每件物品

         {

             sum+=vect[i][k];

             for(int j=(big[i]>>); j>=vect[i][k]; j--)  //每种容量

                 dp[j]=max(dp[j],dp[j-vect[i][k]]+vect[i][k]);   //01背包背一半出来

         }

         ans+=big[i]-dp[big[i]>>];//取其大者

     }

     return ans;

 }

 void init() //初始化

 {

     memset(big,,sizeof(big));

     vect.clear();

     vector<int> tmp;

     for(int i=; i<=m; i++)

         vect.push_back(tmp);

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

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

     {

         if(!m&&!n)  break;

         init();

         for(int i=; i<=m; i++)    scanf("%s",s[i]);    //输入颜色

         for(int i=,t=; i<n; i++)  //输入时间+颜色

         {

             scanf("%d%s",&t,str);

             for(int j=; j<=m; j++) //颜色分类

                 if(strlen(s[j])==strlen(str)&&strcmp(s[j],str)==)

                 {

                     big[j]+=t;

                     vect[j].push_back(t);

                     break;

                 }

         }

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

     }

     return ;

 }

AC代码