算法1
(dp)
看到这题感觉是dp 就用dp写了一下
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010;
int f[N][M];//f[i][j]表示在前i个鱼塘 最后呆在第i个鱼塘 截止时间为j 能钓到最多的鱼的数量
int a[N],d[N],t[N],s[N];
int sum[N][M];//sum[i][j]表示第i个鱼塘到第j分钟时可以钓到多少鱼
int main(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>d[i];
for(int i=2;i<=n;i++)
cin>>t[i];
for(int i=2;i<=n;i++)
s[i]=s[i-1]+t[i];
cin>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]=sum[i][j-1]+max(0,(a[i]-(j-1)*d[i]));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j-t[i]];
if(j>=s[i])
for(int k=s[i-1];k<=j-t[i];k++){
int tt=j-k-t[i];
f[i][j]=max(f[i][j],f[i-1][k]+sum[i][tt]);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i][m]);
cout<<res<<endl;
return 0;
}