題干：

Dearboy was so busy recently that now he has piles of clothes to wash. Luckily, he has a beautiful and hard-working girlfriend to help him. The clothes are in varieties of colors but each piece of them can be seen as of only one color. In order to prevent the clothes from getting dyed in mixed colors, Dearboy and his girlfriend have to finish washing all clothes of one color before going on to those of another color.

From experience Dearboy knows how long each piece of clothes takes one person to wash. Each piece will be washed by either Dearboy or his girlfriend but not both of them. The couple can wash two pieces simultaneously. What is the shortest possible time they need to finish the job?

Input

The input contains several test cases. Each test case begins with a line of two positive integers?M?and?N?(M?< 10,?N?< 100), which are the numbers of colors and of clothes. The next line contains?M?strings which are not longer than 10 characters and do not contain spaces, which the names of the colors. Then follow?N?lines describing the clothes. Each of these lines contains the time to wash some piece of the clothes (less than 1,000) and its color. Two zeroes follow the last test case.

Output

For each test case output on a separate line the time the couple needs for washing.

Sample Input

3 4 red blue yellow 2 red 3 blue 4 blue 6 red 0 0

Sample Output

10

題目大意：

Dearboy和他的女朋友用一個盆一起洗m件衣服，共有n總顏色（每件衣服只有一種顏色）。? 為了放置不同顏色互染，每次只能洗一種顏色的衣服，在這件衣服洗完之前不能洗另外一種衣服。?Dearboy和他女朋友可以同時一起洗衣服，但是不能同時洗同一件衣服，也不能同時洗不同種顏色的衣服。?

一只每件衣服所需時間，問最少花費多少時間可以全部洗完。

（ps：這里建議自己，如果還能看得到這篇題解，自己再讀一遍題，有很多的地方可以幫助自己提升閱讀速度和理解題意，比如The couple can wash two pieces simultaneously. ?這一句剛開始就理解錯了，理解成了可以同時洗兩種，即兩種不能同時一個人洗，但是可以男生洗一種，女票洗一種 這樣。但是其實人家的意思是，可以同時洗兩件，而不是兩種！。因為你看題目區分不同種的用詞是color，而區分每一件，都用的是piece這種的！所以讀到這里不用仔細糾結量詞，直接看上文的這個詞表示的是什么意思，那在這里就表示啥意思了。。。再舉個例子，Each test case begins with a line of two positive integers?M?and?N?(M?< 10,?N?< 100), which are the numbers of colors and of clothes.這句中的the number of 就是英語老師教過的 ? ...的數量 ? 的意思，但是有的題目中，他的意思是，....的編號，因為比如他會說 把1~n這些物品編號成number 1 ~ n ? 所以這時候就要注意一下了！！，the?number of A ?是不是 ?有可能是別的意思）

解題報告：

? ? ? ?poj有毒，，，首先這題卡vector了，優化了很多地方還是只能934ms過。（澄清，，沒卡vector，可以294ms飄過，但是卡memset了，需要你的數組開的不能太大，1e5就剛剛好，開1e6就炸了，tle妥妥的，應該是初始化dp的時候耗時太長了。。）所以還是老老實實的開一個num數組來輔助time這個二維數組的輸入吧、、、相當于替代了vector的time[mp[col]].push_back(tm);這一步，其余的還好。相當于對每一種衣服做0-1背包記一個時間，然后每一種的這個時間求和即可。

AC代碼1：（294ms）（vector + 二維的dp數組）

#include<cstdio> #include<cstring> #include<string> #include<iostream> #include<algorithm> #include<map> #include<vector> using namespace std; map<string ,int> mp; int n,m; int top; int tm;//每種顏色的衣服所洗的總共的時間 int dp[15][100000 + 5]; vector<int> time[50]; int sum[20]; int main() {char col[50];while(scanf("%d%d",&m,&n)) {if(m == 0 && n == 0 ) break;mp.clear();for(int i = 1; i<=20; i++) time[i].clear();memset(dp,0,sizeof dp);memset(sum,0,sizeof sum);top = 0;for(int i = 1; i<=m; i++) {scanf("%s",col);//if(mp.find(col) == mp.end()) mp[col] = ++top;mp[col] = i;}for(int i = 1; i<=n; i++) {scanf("%d%s",&tm,col);time[mp[col]].push_back(tm);sum[mp[col]] += tm;}int ans = 0;for(int k = 1; k<=m; k++) { // memset(dp,0,sizeof(dp));for(int i = 0; i<time[k].size(); i++) {for(int j = sum[k]/2; j>=time[k][i]; j--) {dp[k][j] = max(dp[k][j],dp[k][j-time[k][i]] + time[k][i]);}}ans +=(sum[k] - dp[k][sum[k]/2]);}printf("%d\n",ans); }return 0 ; }

AC代碼2：（63ms）（沒用vector + 一維dp數組）

#include<cstdio> #include<cstring> #include<string> #include<iostream> #include<algorithm> #include<map> #include<vector> using namespace std;int n,m; int top; int tm;//每種顏色的衣服所洗的總共的時間 int dp[100000 + 5]; int num[15]; int time[15][50]; int sum[50]; int main() {char col[50];while(~scanf("%d%d",&m,&n)) {if(m == 0 && n == 0 ) break;map<string, int> mp;memset(num,0,sizeof num); // for(int i = 1; i<=20; i++) time[i].clear();memset(dp,0,sizeof dp);memset(sum,0,sizeof sum);top = 0;for(int i = 1; i<=m; ++i) {scanf("%s",col);mp[col] = i;//if(mp.find(col) == mp.end()) mp[col] = ++top;}for(int i = 1; i<=n; i++) {scanf("%d%s",&tm,col);time[mp[col]][++num[mp[col]]] = tm;sum[mp[col]] += tm;}int ans = 0;for(int k = 1; k<=m; k++) {memset(dp,0,sizeof(dp));for(int i = 1; i<=num[k]; i++) {for(int j = sum[k]>>1; j>=time[k][i]; --j) {dp[j] = max(dp[j],dp[j-time[k][i]] + time[k][i]);}}ans +=(sum[k] - dp[sum[k]>>1]);}printf("%d\n",ans); }return 0 ; }

?

總結

以上是生活随笔為你收集整理的【POJ - 3211】Washing Clothes （dp，0-1背包中点问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。