题目描述
鱼塘钓鱼 DP
DP 复杂度 $O(t*n^2)$
dp[i][j]:第i个鱼塘第j分钟的最大值
枚举当前鱼塘钓鱼时间 取最大值
如果当前鱼塘钓鱼x分钟 x分钟可以钓鱼sum(x)条 从上个鱼塘转移到这个鱼塘需要m分钟
则转移方程为dp[i][j]=max(dp[i-1][j-m-x]+sum(x))
C++ 代码
#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
int dp[105][1005];
int f[105],d[105],ne[105];
signed main()
{
for(int i=0;i<105;i++)
for(int j=0;j<1005;j++)
dp[i][j]=INT_MAX+1;
int N;cin>>N;
for(int i=1; i<=N; i++)
cin>>f[i];
for(int i=1; i<=N; i++)
cin>>d[i];
for(int i=1; i<N; i++)
cin>>ne[i];
int T;cin>>T;
int ans=0;
for(int i=0;i<=T;i++)
dp[0][i]=0;
dp[1][0]=0;
for(int i=1; i<=N; i++)
{
for(int j=1;j<=T;j++)
{
int base=j-ne[i-1];
if(base<0)continue;
dp[i][j]=dp[i-1][base];
int tmp=f[i];int tot=tmp;
while(tmp>0&&base>0)
{
base--;
dp[i][j]=max(dp[i][j],dp[i-1][base]+tot);
tmp-=d[i];
tot+=tmp;
}
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
}