Posted on 2007-02-17 13:58
oyjpart 阅读(1626)
评论(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;
}