题意: 有个人要去湖里钓鱼, 总共有 N 个湖, 排成一个序列, 用字母 P 表示湖, 从湖 pi 到 pi+1(下一个湖) 需要 ti 个五分钟.
并且, 每个湖里可钓出来的鱼每过五分钟就减少 di. 如果产出的鱼小于等于 di. 那么下个五分钟这个湖再也不会产出鱼.
问: 使得总的钓出鱼数目最大和每个湖花费的对应时间,. 如果鱼数目最大存在多种解, 让时间尽可能花费在前面的湖上.
解法:
枚举每一个 pi, 划去从 p0 至 pi 的总 time(总的转移时间).
这样我们就可以在任意 p0-pi 之间钓鱼而不用考虑 time 的问题. 剩下的 h 全部花费在钓鱼上.
每次花费的五分钟都花在产出鱼数目最大的湖上. 这样得到总鱼数目总是最大的. 如果所有的鱼都钓完还有时间剩余. 全部加在第一个湖上面.
- #include <string>
- #include<iostream>
- #include<map>
- #include<memory.h>
- #include<vector>
- #include<algorithm>
- #include<queue>
- #include<vector>
- #include<stack>
- #include<math.h>
- #include<iomanip>
- #include<bitset>
- #include"math.h"
- namespace cc
- {
- using std::cout;
- using std::endl;
- using std::cin;
- using std::map;
- using std::vector;
- using std::string;
- using std::sort;
- using std::priority_queue;
- using std::greater;
- using std::vector;
- using std::swap;
- using std::stack;
- using std::queue;
- using std::bitset;
- class State
- {
- public:
- int curFish;
- int d;
- int time;
- int index;
- State() {}
- State(int curFish, int d, int time, int index) :
- curFish(curFish), d(d), time(time), index(index)
- {
- }
- friend bool operator <(const State& s1, const State& s2)
- {
- if (s1.curFish != s2.curFish)
- return s1.curFish < s2.curFish;
- return s1.index> s2.index;
- }
- };
- constexpr int N = 32;
- int H = 0;
- int n;
- int totalFish;
- int per[N] = { 0 };
- State states[N];
- priority_queue <State>q;
- void solve()
- {
- int t = 0;
- while (cin>> n && n)
- {
- if (t != 0)
- cout <<endl;
- ++t;
- cin>> H;
- H = H * 12;
- int f = 0;
- for (int i = 0;i <n;i++)
- {
- cin>> f;
- State state(f, 0, 0, i);
- states[i] = state;
- }
- for (int i = 0;i <n;i++)
- {
- cin>> states[i].d;
- }
- for (int i = 1;i <n;i++)
- {
- cin>> states[i].time;
- states[i].time = states[i].time + states[i-1].time;
- }
- totalFish = -1;
- memset(per, 0, sizeof(per));
- for (int i = 0;i <n;i++)
- {
- while (q.empty() == false)
- q.pop();
- for (int k = 0;k <= i;k++)
- q.push(states[k]);
- int h = H;
- int curTotalFish = 0;
- int times[N] = {0};
- h = h - states[i].time;
- while (h> 0)
- {
- State s = q.top();
- q.pop();
- int f = s.curFish;
- if (f <= 0)break;
- --h;
- s.curFish -= s.d;
- curTotalFish += f;
- times[s.index]++;
- q.push(s);
- }
- if (h> 0)
- times[0] += h;
- if (curTotalFish> totalFish)
- {
- totalFish = curTotalFish;
- memcpy(per, times, sizeof(times));
- }
- }
- cout << per[0] * 5;
- for (int i=1;i<n;i++)
- cout<<"," << per[i] * 5;
- cout << endl;
- cout << "Number of fish expected:" << totalFish << endl;
- }
- }
- };
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("d://1.text", "r", stdin);
- #endif // !ONLINE_JUDGE
- cc::solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2974457.html