原题链接：1262. 鱼塘钓鱼 - AcWing题库
有 N个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5 时，如下表：
鱼塘编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
第1分钟能钓到的鱼的数量（1..1000） | 10 | 14 | 20 | 16 | 9 |
每钓鱼1分钟钓鱼数的减少量（1..100) | 2 | 4 | 6 | 5 | 3 |
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟） | 3 | 5 | 4 | 4 |
即：在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼，第 2分钟内只能钓到 8 条鱼，……，第 5 分钟以后再也钓不到鱼了。
从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟，从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟，……
给出一个截止时间 T，设计一个钓鱼方案，从第 1 个鱼塘出发，希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。
输入格式
共 5 行，分别表示：
第 1 行为 N；
第 2 行为第1 分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；
第 3 行为每过 1 分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；
第 4 行为当前鱼塘到下一个相邻鱼塘需要的时间；
第 5 行为截止时间 T。
输出格式
一个整数（不超过2^31−1），表示你的方案能钓到的最多的鱼。
数据范围
1≤N≤100 1≤T≤1000
输入样例：
代码语言：javascript复制5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14输出样例：
代码语言：javascript复制76暴力枚举法：
由于此题数据量很小可以进行暴力枚举，当前鱼塘可以掉一会时间，当到达转移时间时，可以花费c[i]去转移到下一个鱼塘，获得更多的鱼，dp[i][j]=dp[i 1][k] dp[i][j-k-c[i]];
代码语言：javascript复制#include<iostream>
#include<string>
using namespace std;
int n,t;
bool flag=0;
int a[105],a1[105],b[105],c[105];
int dp[105][1005];
int main(){
cin>>n;
for(int i=1;i<=n;i )cin>>a[i];
for(int i=1;i<=n;i )cin>>b[i];
for(int i=1;i<n;i )cin>>c[i];
cin>>t;
for(int i=1;i<=n;i ){
for(int j=1;j<=t;j ){
dp[i][j]=dp[i][j-1] a[i];
a[i]=max(a[i]-b[i],0);
}
}
for(int i=n-1;i>=1;i--){//逆序枚举鱼塘个数，因为下面要处理第i 1个鱼塘，i 1要先于i更新
for(int j=t;j>=c[i];j--){//j为总时间，花费最少c[i]，用来走到下一个鱼塘
int maxx=dp[i][j];
for(int k=0;k<=j-c[i];k ){
//可以给i 1个分配k个时间，那么剩下j-k-c[i]为第i个鱼塘的时间
maxx=max(maxx,dp[i 1][k] dp[i][j-k-c[i]]);
}
dp[i][j]=maxx;
}
}
cout<<dp[1][t]<<endl;
return 0;
}贪心：
这个题我们可以把一个鱼塘可以钓的鱼数全部列举出来，从中选取k大的数即为答案，这个k又是啥，我们的总时间T可以分为路程时间 钓鱼时间，我们枚举一下最多到哪一个终点，此时路程时间便可以知道，那么钓鱼的时间=总时间T-路程时间，注释附在代码上。
代码语言：javascript复制#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
int n,t,res;
int a[N],b[N],c[N],s[N];
//a表示第 1分钟各个鱼塘能钓到的鱼的数量，b表示鱼减少的数量
//c表示到达各个鱼塘时间，s表示在第i个鱼塘钓的时间
int get(int k){//在第k个鱼塘可以钓的鱼数
return max(0,a[k]-b[k]*s[k]);//初始a[k]，每次减少b[k]，钓了s[k]分钟
//所以此时可以在第k个鱼塘钓a[k]-b[k]*s[k]个，但不能小于0
}
//多路归并，每一次寻找可以钓的最大鱼数
int work(int n,int t){//n表示最多移动到第n个鱼塘，t表示钓鱼的时间
int res=0;
memset(s,0,sizeof(s));//初始都为0
for(int i=1;i<=t;i ){//枚举每一分钟
int m=1;//记录最大下标
for(int j=2;j<=n;j ){//枚举1-n的鱼塘数
if(get(m)<get(j)){//第j个鱼塘所获得的鱼数小于第m个鱼塘所获得的鱼数，则更新下标
m=j;
}
}
res =get(m);
s[m] ;//在第m个上钓鱼要花费时间
}
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i )cin>>a[i];
for(int i=1;i<=n;i )cin>>b[i];
for(int i=2;i<=n;i ){
cin>>c[i];
c[i] =c[i-1];//前缀和求花费移动鱼塘的时间
}
cin>>t;
for(int i=1;i<=n;i ){//枚举第一个鱼塘到第i个鱼塘最大获得多少鱼
res=max(res,work(i,t-c[i]));//t-c[i]表示总时间减去移动花费的时间，剩下为钓鱼的时间
}
cout<<res<<endl;
return 0;
}这样时间复杂度会大大优化，如果数据量再大一点，暴力枚举就会寄了
此题贪心思路按照y总的讲解写的，里面涉及了多路归并等算法，此题还有更多解法，不再一一介绍了，文章尚有不足，欢迎大佬们指正。
