AcWing 1262. 鱼塘钓鱼（每日一题）

本文主要是介绍AcWing 1262. 鱼塘钓鱼（每日一题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

暴力枚举法：

贪心：

原题链接：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

输入样例：

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

输出样例：

暴力枚举法：

由于此题数据量很小可以进行暴力枚举，当前鱼塘可以掉一会时间，当到达转移时间时，可以花费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));//初始都为0for(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;
}

这样时间复杂度会大大优化，如果数据量再大一点，暴力枚举就会寄了