好贷网好贷款

poj 3211 Washing Clothes

发布时间:2016-12-3 14:51:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3211 Washing Clothes",主要涉及到poj 3211 Washing Clothes方面的内容,对于poj 3211 Washing Clothes感兴趣的同学可以参考一下。

     这题一看给我的感觉就是搜索,对每种的情况进行搜索,找出最接近洗此种颜色衣服花费时间一般(小于等于),然后洗此种衣服的总时间减去搜索的这个结果,就是洗这种衣服需要花费的最少时间。然后按着类别分别进行搜索,然后加起来就是总共需要的时间。看了下别人的思路,发现背包也完全可以实现,并且时间更加短,dp可以避免重复搜索,所以自己写了个do的。 #include<cstdio> #include<cstring> #include<iostream> #include<string> using namespace std; const int N = 105; int n,m; typedef struct { int col,t; }Node; Node arr[N]; int sum[11]; string color[11]; int main(void) { while(scanf("%d %d",&m,&n)) { memset(sum,0,sizeof(sum)); if(m==0&&n==0) break; for(int i=1;i<=m;++i) cin>>color[i]; for(int i=1;i<=n;++i) { string str; cin>>arr[i].t>>str; int j; for(j=1;j<=m;++j) if(color[j]==str) break; arr[i].col = j; sum[j] += arr[i].t; } int ans = 0; bool dp[100000]; for(int i=1;i<=m;++i)//按照颜色来进行分类 { memset(dp,false,sizeof(dp)); dp[0] = true; for(int j=1;j<=n;++j) { if(arr[j].col==i) { for(int k=sum[i];k>=arr[j].t;k--) if(dp[k-arr[j].t]) { dp[k] = true; } } } int flag = sum[i]/2; int k; for(k=flag;k>=0;--k) if(dp[k]) { break; } ans += (sum[i]-k); } cout<<ans<<endl; } return 0; }

上一篇:Linux中的hangcheck-timer模块
下一篇:WINCE6.0+S3C2443下SD卡驱动

相关文章

相关评论