posts - 21,  comments - 9,  trackbacks - 0

贪心算法,使用STL的priority_queue来维护一个队列。保证鱼数最多(相同鱼则保存标号较小的)的一个序列。然后贪心就可以了。一下是代码
#include<iostream>
#include<queue>
using namespace std;
int n,h;
int f[30],t[30],d[30];
int best[30],way[30],maxinum,tot,tag=0;
struct node
{
 int num;
 int fish;
 void set(int id,int f)
 {
  num=id;
  fish=f;
 }
};
bool operator<(const node a,const node b)
{
 if(a.fish==b.fish)
  return a.num>b.num;
 else
  return a.fish<b.fish;
}
priority_queue<node> qu;
node now;
int main()
{
 while(scanf("%d",&n)&&n)
 {
  if(tag)
   printf("\n");
  cin>>h;
  h*=12;
  maxinum=-1;
  int i,j;
  for(i=0;i<n;i++)
  {
   cin>>f[i];
  }
  for(i=0;i<n;i++)
  {
   cin>>d[i];
  }
  for(i=0;i<n-1;i++)
  {
   cin>>t[i];
  }
  ///////////数据输入完毕,开始进入计算
  for(i=0;i<n;i++)
  {
   memset(way,0,sizeof(way));
   while(!qu.empty())
    qu.pop();
   if(i>0)
    h-=t[i-1];
   tot=0;   
   for(j=0;j<=i;j++)
   {
    now.set(j,f[j]);
    qu.push(now);    
   }
   for(j=0;j<h;j++)
   {
    now=qu.top();
    qu.pop();
    tot+=now.fish;
    now.fish-=d[now.num];
    if(now.fish<0)
     now.fish=0;
    way[now.num]+=5;
    qu.push(now);
   }
   if(tot>maxinum)
   {
    maxinum=tot;
    memcpy(best,way,sizeof(way));
   }

  }
  printf("%d",best[0]);
  for(i=1;i<n;i++)
   printf(", %d",best[i]);
  printf("\nNumber of fish expected: %d\n",maxinum);
  tag=1;
 }
 return 0;

}

posted on 2010-08-21 15:09 崔佳星 阅读(1466) 评论(1)  编辑 收藏 引用 所属分类: POJ

FeedBack:
# re: pku 1042
2010-08-29 17:55 | Tanky Woo
朋友你好:
C/C++和算法论坛:C++奋斗乐园
欢迎你加入。
里面有C/C++交流,求助,源码,
算法学习,求助,
ACM刷题
等各种板块,
相信大家在一起能学习快乐。

论坛地址:
[url=http://www.cppleyuan.com/index.php">http://www.cppleyuan.com/index.php]http://www.cppleyuan.com/index.php">http://www.cppleyuan.com/index.php[/url]

另外,论坛现在招收版主,有意 愿的朋友可以看看:
[url=http://www.cppleyuan.com/forumdisplay.php?fid=44">http://www.cppleyuan.com/forumdisplay.php?fid=44]http://www.cppleyuan.com/forumdisplay.php?fid=44">http://www.cppleyuan.com/forumdisplay.php?fid=44[/url]

注:此留言绝不是广告,只是看见博主也是C/C++和算法的爱好者,我们想邀请博主一起加入我们的论坛。

我也是一名C/C++和ACM爱好者,大家可以去我博客看看就知道了:
[url=http://www.wutianqi.com/">http://www.wutianqi.com/]http://www.wutianqi.com/">http://www.wutianqi.com/[/url]

打扰之处请见谅。
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜