POJ 1042 Gone Fishing-白红宇

POJ 1042 Gone Fishing

阅读量：5080 次

发布时间：2019-06-12

本文共 1675 字，大约阅读时间需要 5 分钟。

题意：一个人要在n个湖中钓鱼，湖之间的路径是单向的，只能走1->2->3->...->n这一条线路，告诉你每个湖中一开始能钓到鱼的初始值，和每钓5分钟就减少的数量，以及湖之间的距离，问用h小时最多钓多少鱼。鱼的数量不会增加，而且如果不钓鱼的话鱼的数量不会减少，如果有多个答案，输出在小号的湖上花费时间最多的答案。

解法：贪心。枚举在前i个湖里钓鱼，那么走的路程就是一定的，用总时间减去走过的时间，剩下的时间每5分钟为一个单位，选鱼最多的湖钓，然后更新湖里鱼的数量。据说dp也可以做，大概想到了但是觉得好麻烦没有写……以下是我的想法……欢迎指正：可以用一个结构体dp数组，结构体里存鱼数和时间，dp[i][j]表示在前i个湖里钓鱼用了j时间时钓到的鱼数和在第i个湖用的时间，应该就可以了吧……

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;struct node{ int f, d, id; bool operator < (const node &tmp) const { if(f == tmp.f) return id > tmp.id; else return f < tmp.f; }}l[30];int sum[30];int ans[30][30];int main(){ int n, h; while(~scanf("%d", &n) && n) { scanf("%d", &h); memset(sum, 0, sizeof sum); memset(ans, 0, sizeof ans); for(int i = 1; i <= n; i++) { scanf("%d", &l[i].f); l[i].id = i; } for(int i = 1; i <= n; i++) scanf("%d", &l[i].d); for(int i = 2; i <= n; i++) { int x; scanf("%d", &x); sum[i] = sum[i - 1] + x; } int st = h * 12; int maxn = -1, pos = 0; for(int i = 1; i <= n; i++) { priority_queue 
                   
                     q; for(int j = 1; j <= i; j++) q.push(l[j]); int res = 0; for(int j = 0; j < st - sum[i]; j++) { node tmp = q.top(); q.pop(); res += tmp.f; ans[i][tmp.id]++; q.push((node){max(0, tmp.f - tmp.d), tmp.d, tmp.id}); } if(res > maxn) { maxn = res; pos = i; } } for(int i = 1; i <= n; i++) { if(i != 1) printf(", "); printf("%d", ans[pos][i] * 5); } puts(""); printf("Number of fish expected: %d\n\n", maxn); } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4846145.html

你可能感兴趣的文章