首页 > 代码库 > [POJ 3211] Washing Clothes (动态规划)
[POJ 3211] Washing Clothes (动态规划)
题目链接：http://poj.org/problem?id=3211
题意：有M件衣服，每种衣服有一种颜色，一共有N种颜色。现在两个人洗衣服，规则是必须把这一种颜色的衣服全部洗完才能去洗下一种颜色的衣服。
问：在两个人可以同时洗衣服的情况下，把衣服全部洗完最少需要多久。
如果说两个人同时洗同一种颜色衣服，那么最少的时间就是洗完该颜色衣服的总时间的一半。
那么我们可以将洗每种衣服分开来看，视作一个01背包，容量是洗该颜色衣服的总时间的一半。
然后最多花多久。那么该颜色的总时间-这个人花的最多时间就是另一个洗这种颜色衣服的时间。
最后求最大的。
代码：
1 import java.util.*; 2 3 public class Main{ 4 static HashMap<String,Integer> hs; 5 public static void main(String[] args){ 6 Scanner cin = new Scanner(System.in); 7 while( true ){ 8 int N = cin.nextInt(); 9 int M = cin.nextInt();10 11 if( N==0&&M==0 ) break;12 13 int c[][] = new int[N+1][M+1];14 15 hs = new HashMap<String,Integer>();16 17 for(int i=1;i<=N;i++){18 String s = cin.next();19 hs.put(s, i);20 }21 22 int sum[] = new int[N+1];23 24 int sumn = 0;25 26 for(int i=1;i<=M;i++){27 int ta = cin.nextInt();28 String tb = cin.next();29 int x = hs.get(tb);30 c[x][++c[x][0]] = ta;31 sum[x] += ta;32 sumn += ta;33 }34 35 int dp[][] = new int[N+1][sumn+100];36 int ans = 0;37 for(int i=1;i<=N;i++){38 for(int k=1;k<=c[i][0];k++){39 for(int j=sum[i]/2;j>=c[i][k];j--){40 if( j>=c[i][k] )41 dp[i][j] = Math.max(dp[i][j],dp[i][j-c[i][k]]+c[i][k]);42 }43 }44 ans += dp[i][sum[i]/2];45 }46 47 System.out.println(Math.max(ans,sumn-ans)); 48 49 }50 }51 }
[POJ 3211] Washing Clothes (动态规划)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。