线性dp

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1005;
int a[N],s[N],t[N];//个数，减少量，时间
int f[N][M];
int d[N];//时间前缀和
int n,T;
//计算鱼的收获
int solve(int x,int y){
    int res=0;
    int cnt=a[x];//当前一分钟的钓鱼数量
    for(int i=1;i<=y;i++){
        if(cnt<=0) break;//没有鱼了
        res+=cnt;
        cnt-=s[x];//鱼的数量减少
    }
    return res;
}
int main(){
    //加速用的，可以删掉
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int i=1;i<=n-1;i++){
        cin>>t[i];
    }
    cin>>T;
    d[1]=0;
    //计算时间前缀和
    for(int i=2;i<=n;i++){
        d[i]=d[i-1]+t[i-1];
    }
    memset(f,0xcf,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        int tmp1=d[i];//走到需要的时间
        int tmp2=T-tmp1;//剩余钓鱼时间
        if(tmp2<0) continue;
        for(int j=0;j<=tmp2;j++){//给j分钟在前i个鱼塘钓鱼
            f[i][j]=f[i-1][j];
            for(int k=1;k<=j;k++){//给第i个鱼塘分配k分钟
                if(f[i-1][j-k]==0xcfcfcfcf) continue;
                int v=solve(i,k);//计算时间
                f[i][j]=max(f[i][j],f[i-1][j-k]+v);
            }
        }
    }
    //计算最优解
    int ans=0;
    for(int i=1;i<=n;i++){
        int tmp=T-d[i];
        if(tmp>=0){
            ans=max(ans,f[i][tmp]);
        }
    }
    cout<<ans;
    return 0;
}

优先队列

#include<bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=110;
int a[N],b[N],d[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,T;
	cin>>n;
	//获取初始的鱼塘中鱼的数量 
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//获取公差
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	//d[i]表示从第一个鱼塘到第i个鱼塘的时间 
	for(int i=2;i<=n;i++){
		cin>>d[i];
		d[i]+=d[i-1];
	}
	cin>>T;
	int ans=0;
	for(int i=1;i<=n;i++){
		int time=T-d[i];
		priority_queue<PII> q;
		for(int k=1;k<=i;k++){
			q.push({a[k],k});//将前i个池塘放入优先队列中 
		}
		int fish=0;//总的钓鱼的数量 
		while(q.size()&&time>0){
			PII t=q.top();
			q.pop();
			int tmp=t.y;
			fish+=t.x;
			time--;
			t.x-=b[tmp];
			if(t.x>0){
				q.push(t.x,tmp);//放入钓了以后新时刻可以调到的鱼的数量
			}
		}
		ans=max(ans,fish);
	}
	printf("%d",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
#define x first
#define y second
int a[N],b[N],spend[N]; 
int main()
{
	int n,T;
	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>>spend[i];
		spend[i]+=spend[i-1];//spend[i]表示从第一个鱼塘到第i个鱼塘的时间 
	}
	cin>>T;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int fish_time=T-spend[i];
		priority_queue<PII> q; 
		for(int k=1;k<=i;k++)
		{
			q.push({a[k],k});//将前i个池塘放入优先队列中 
		}	
		int fish=0;//总的钓鱼的数量 
		while(q.size()&&fish_time>0)
		{
			PII t=q.top();
			q.pop();
			int id=t.y;	
			fish+=t.x;
			fish_time--;
			t.x-=b[id];
			if(t.x>0)
			{
				q.push({t.x,id});//放入钓了以后新时刻可以调到的鱼的数量	
			} 
		}
		ans=max(ans,fish); 
	} 
	cout<<ans;
	return 0;
	
}