1 solutions
-
1
我转了一圈,竟然没人发题解?那行吧,我来发主要思想:(
没有贪心)模拟我们来看看最关键的点:如何才能确定怎么才能钓到最多的鱼?
方法很简单,就是一个个去试,试到更好的就选更好的
大家是不是都在往贪心上想?所以才忽略了这种方法?但是就纯纯这样模拟的话,恐怕会TE,甚至WA,所以还要一点点剪枝。
也很简单,时间不够跳出就行。 (如果肆意让时光流逝,就可能会导致鱼量变成负数或者直接死循环)
好了,讲了这么多,附上代码(有详细注释)
#include <bits/stdc++.h> #define SIZE 1000 using namespace std; struct fish { int a,b,c,d; }; fish fisher[SIZE]; int n,h; int main() { cin >> n >> h; h *= 12;//这里乘以12而不是60是为了规避5分钟带来的影响 for(int i = 1;i <= n;i++) cin >> fisher[i].a;//每个湖第一个5分钟能钓到鱼的数量 for(int i = 1;i <= n;i++) cin >> fisher[i].b;//以后的每5分钟钓鱼数量比前一个 5 分钟钓鱼数量减少的数量 for(int i = 1;i < n;i++) cin >> fisher[i].c;//由第i个湖到第i+1个湖所需要的时间 //特别注明:fisher[i].d表示这个湖第i个5分钟能钓到的鱼数 int sum = 0,ans = -1,maxn,H,l; for(int i = 1;i <= n;i++) { for(int j = 1;j <= i;j++) fisher[j].d = fisher[j].a; h -= fisher[i - 1].c;//要去到这个湖,先要花掉时间 H = h;if(h < 0) break;/*如果时间不够,就跳出*/sum = 0; while(H--) { maxn = 0; for(int k = 1;k <= i;k++) { if(maxn < fisher[k].d) { l = k; maxn = fisher[k].d; } } sum += maxn;//sum将所有能钓到的鱼的最大值全部统计到一起 fisher[l].d -= fisher[l].b;//更新fisher[i].d } ans = max(ans,sum);//先考虑去了这个湖,再看能不能钓到更多的鱼 } cout << ans << endl; return 0; }
后语:希望能有神犇们发一些时间复杂度低一点的代码
- 1
Information
- ID
- 10
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 9
- Tags
- # Submissions
- 215
- Accepted
- 10
- Uploaded By