POJ 3211 Washing Clothes

題目大意：有一男一女一起洗衣服， 衣服有不同的顏色和洗每件衣服要花一定的時間， 為了不讓衣服染色洗的時候2人只能洗完1種顏色的才能洗下一種，要求求出洗完2人洗完衣服的最短時間。

思路：這題可以根據POJ 1014得出思路，對於每種顏色洗它都有一個總時間，要求洗這種顏色的最少時間，就是求看能不能一個人洗這種顏色的衣服達到總時間的一半。

code：
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
struct node 
{ 
    int time; 
    char str[12]; 
}Lnode[102]; 
int s = 0, num[12], dp[102*1002]; 
int cmp(void const *a, void const *b) 
{ 
    return strcmp((*(struct node *)a).str,(*(struct node *)b).str); 
} 
int DP(int n, int count) 
{ 
    int i = 0, j = 0, ave = num[count]/2; 
    memset(dp, 0, sizeof(dp)); 
    for(i = s; i<n; i++) 
    { 
        for(j =ave; j>=Lnode[i].time; j--) 
            dp[j] = dp[j]>dp[j-Lnode[i].time]+Lnode[i].time? dp[j]:dp[j-Lnode[i].time]+Lnode[i].time; 
    } 
    s = n; 
    return num[count]-dp[ave]; 
} 
int main() 
{ 
    int i = 0, n = 0, m = 0, sum = 0, count = 0; 
    char str[12]; 
    while(scanf("%d %d", &m, &n), n+m) 
    { 
        getchar(); 
        for(i = 0; i<m; i++) 
            scanf("%s", str); 
        for(i = 0; i<n; i++) 
        { 
            getchar(); 
            scanf("%d %s",&Lnode[i].time, Lnode[i].str); 
        } 
        getchar(); 
        memset(num, 0, sizeof(num)); 
        sum = count = s = 0; 
        qsort(Lnode, n, sizeof(Lnode[0]), cmp); 
        num[0] = Lnode[0].time; 
        for(i = 1; i<n; i++) 
        { 
            if(strcmp(Lnode[i].str, Lnode[i-1].str) == 0) 
                num[count] += Lnode[i].time; 
            else  www.2cto.com
            { 
                sum += DP(i, count); 
                count++; 
                num[count] = Lnode[i].time; 
            } 
        } 
        sum += DP(i, count); 
        printf("%d\n", sum); 
    } 
    return 0; 
}