为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 274491
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 struct node
 5 {
 6     int h,c,a;
 7 }a[410];
 8 int dp[40010];
 9 bool cmp(const node & n1,const node & n2)
10 {
11     return n1.a<n2.a;
12 }
13 
14 int main()
15 {
16     int k;
17     int maxHeight=0;
18     cin>>k;
19     for(int i=1;i<=k;i++)
20     {
21         cin>>a[i].h>>a[i].a>>a[i].c;
22         maxHeight=max(maxHeight,a[i].a);
23     }
24     sort(a+1,a+1+k,cmp);
25     memset(dp,0,sizeof(dp));
26     dp[0]=1;
27     for(int i=1;i<=k;i++)
28     {
29         for(int j=a[i].a-a[i].h;j>=0;j--)
30         {
31             if(dp[j])
32             {
33                 for(int t=1;t<=a[i].c;t++)
34                 {
35                     if(j+t*a[i].h>a[i].a) break;
36                     dp[j+t*a[i].h]=1;
37                 }
38             }
39         }
40     }
41     while(maxHeight)
42     {
43         if(dp[maxHeight]) break;
44         maxHeight--;
45     }
46     cout<<maxHeight<<endl;
47 }

posted on 2010-08-06 15:21 baby-fly 阅读(280) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理