oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

PKU1042 Gone Fishing

Posted on 2007-02-17 13:58 oyjpart 阅读(1621) 评论(0)  编辑 收藏 引用

简单题 直接枚举结束湖泊+贪心选择就可以了
为什么可以贪心?(反正你要取的是最优解 你可以假定自己知道最优解 一路走过去的路上就直接取最优解就可以了)
因为集训的时候这个题目莫名WA 故再A一遍 以解心头之恨!
using namespace std; 不能用time G++ CE多次 faint
Gone Fishing
Solution:
// by oyjpArt
#include <iostream>
#include <queue>
using namespace std;
const int N = 30;
struct node {int nf, idx; void set(int nn, int ii) {nf = nn; idx = ii;}};
int nl, time, f[N], t[N], d[N], totf, stay[N], beststay[N];
typedef priority_queue<node> PQ;

bool operator<(const node&a, const node& b) { if(a.nf == b.nf) return a.idx > b.idx; return a.nf < b.nf; }

int main () {
 int i, j;
 while(scanf("%d", &nl), nl) {
  scanf("%d", &time);
  time *= 12;
  int maxf = -1;
  for(i = 0; i<nl; i++) scanf("%d", f+i);
  for(i = 0; i<nl; i++) scanf("%d", d+i);
  for(i = 0; i<nl-1; i++) scanf("%d", t+i);
  for(i = 0; i<nl; i++) { 
   memset(stay, 0, sizeof(stay));
   totf = 0;
   if(i>0) time -= t[i-1];
   node now;
   PQ pq;
   for(j = 0; j<=i; j++)
   { now.set(f[j], j); pq.push(now);}
   for(j = 0; j<time; j++) {
    now = pq.top();
    pq.pop();
    stay[now.idx] += 5;
    totf += now.nf;
    now.nf -= d[now.idx];
    if(now.nf < 0) now.nf = 0;
    pq.push(now);
   }
   if(totf > maxf) {
    maxf = totf;
    memcpy(beststay, stay, sizeof(stay));
   }
  }
  printf("%d", beststay[0]);
  for(i = 1; i<nl; i++) printf(", %d", beststay[i]);
  printf("\nNumber of fish expected: %d\n\n", maxf);
 }
 return 0;
}


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