原题链接

ACwing

思路

显然，一个最优的方案一定是依次在若干个鱼塘钓鱼，没有往返路途（否则，返回时所钓的鱼可以在第一次位于该鱼塘时钓出）。问题在与，如何求出最优的一个鱼塘序列？确定了一个鱼塘序列之后，应该在每一个鱼塘钓多少鱼？

确定在哪些鱼塘钓鱼是困难的，但是我们可以枚举可能的鱼塘。确定了鱼塘序列之后，类比多路归并的思路，显然我们可以在复杂度内确定在哪一个池塘钓鱼（求解的值并不是时间连续的，但是显然可以排列成一个合法的序列）。

最终的时间复杂度是。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
struct node{
    int val;
    int sub;
    friend bool operator < (const node &n1, const node & n2){
        return n1.val<n2.val;
    }
};

node d[N];
int road_time [N];
priority_queue<node, vector<node> >pq;


int solve(int arr_len, int tot_time){
    int cur_time = tot_time;
    int ans = 0;
    
    for(int i=0;i<arr_len;i++){
        cur_time = tot_time;
        for(int j=1;j<=i;j++){
            cur_time -= road_time[j];
            if(cur_time<0)return ans;
        }
        
        while(pq.size())pq.pop();
        for(int j=0;j<=i;j++){
            pq.push(d[j]);
        }
        
        int tem_ans = 0;
        while(pq.size() && cur_time >0){
            cur_time --;
            node topnode = pq.top();pq.pop();
            tem_ans += topnode.val;
            if(topnode.val-topnode.sub>0){
                pq.push(node{topnode.val-topnode.sub, topnode.sub});
            }
        }
        ans = max(ans, tem_ans);
    }
    return ans;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>d[i].val;
    }
    
    for(int i=0;i<n;i++){
        cin>>d[i].sub;
    }
    
    for(int i=1;i<n;i++){
        cin>>road_time[i];
    }
    
    int tot_time;
    cin>>tot_time;
    cout<<solve(n,tot_time)<<endl;
    return 0;
}