Posted on 2007-02-17 13:58
oyjpart 閱讀(1634)
評(píng)論(0) 編輯 收藏 引用
簡(jiǎn)單題 直接枚舉結(jié)束湖泊+貪心選擇就可以了
為什么可以貪心？（反正你要取的是最優(yōu)解 你可以假定自己知道最優(yōu)解 一路走過去的路上就直接取最優(yōu)解就可以了）
因?yàn)榧?xùn)的時(shí)候這個(gè)題目莫名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;
}