题目链接:http://poj.org/problem?id=3211
题意:Dearboy夫妇有一桶衣服要清洗,由于衣服颜色不同,质量也不太好,为了防止不同颜色的衣服混合清洗造成染色,所以Dearboy夫妇只能在清洗完一种颜色的衣服后再清洗另一种颜色的衣服(注意理解:如果Dearboy的老婆已经把蓝色衣服洗好了,但Dearboy洗的那一件蓝色衣服还没有清洗好,Dearboy的老婆只能等着,等Dearboy把他洗的蓝色衣服洗好了,才能一起再去洗黄色的衣服)。现有M种颜色的衣服N件,每件衣服的清洗需要的时间和颜色题目告知,问Dearboy夫妇至少需要多少时间能把衣服清洗干净。
思路:由于Dearboy夫妇只能在清洗完一种颜色的衣服后才能清洗另一种颜色的衣服,所以就要求Dearboy夫妇再清洗一种颜色的衣服时花的时间尽可能的相同。假设清洗一种颜色的衣服需要的额总时间为sumtime,将sumtime/2的背包尽可能的装满,清洗该种衣服所需要的时间则为sumtime-dp[sumtime/2](以时间长的一个为准);
代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXM 15
#define MAXN 105
int M,N,ans;
char color[MAXM][11];
int dp[50005];
struct Close{
int time;
char col[11];
int used;
}close[MAXN];
int max(int a,int b)
{
return a>b ? a : b ;
}
int main()
{
int i,j;
while(scanf("%d%d",&M,&N) && (M!=0&&N!=0))
{
ans =0;
for(i=0;i<M;i++)
scanf("%s",color[i]);
for(i=0;i<N;i++)
{
scanf("%d %s",&close[i].time,&close[i].col);
close[i].used=0;
}
int temp[105];
for(i=0;i<M;i++)//一种颜色一种颜色的清洗
{
int num=0;
int sumtime=0;
for(j=0;j<N;j++)//求出一种颜色的衣服总共要花费多少时间清洗(sumtime)
{
if(close[j].used)
continue;
if(strcmp(color[i],close[j].col) == 0)
{
temp[num++]=close[j].time;
sumtime += close[j].time;
close[j].used = 1;
}
}
for(int l=0;l<=sumtime/2;l++)
dp[l]=0;
for(int k=0;k<num;k++)//背包sumtime/2最大装满
for(int v=sumtime/2;v>=temp[k];v--)
{
dp[v] = max(dp[v],dp[v-temp[k]]+temp[k]);
}
ans += sumtime - dp[sumtime/2];//清洗一种颜色衣服需要花费的时间
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
POJ3211--Washing Clothes
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
+ 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table ...
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ2676-Sudoku 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
西北工业大学POJ试题C++答案代码+课程设计
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
网上整理的一些poj刷题指南。 poj地址:http://poj.org
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
<1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 双背包求最优值 构造三角形问题 带上下界限制的背包问题(012背包) 3.线性的动态规划问题 <1>积木游戏...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...