有 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
输入样例：
5 10 14 20 16 9 2 4 6 5 3 3 5 4 4 14
输出样例：
76
暴力枚举法：
由于此题数据量很小可以进行暴力枚举，当前鱼塘可以掉一会时间，当到达转移时间时，可以花费c[i]去转移到下一个鱼塘，获得更多的鱼，dp[i][j]=dp[i+1][k]+dp[i][j-k-c[i]];
#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-路程时间，注释附在代码上。
#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总的讲解写的，里面涉及了多路归并等算法，此题还有更多解法，不再一一介绍了，文章尚有不足，欢迎大佬们指正。
