如果数据是这样的:
3
1
10 15 50
0 3 4
1 2
那么不应该是先花15分钟到第3个湖,然后花45分钟都在第3个湖钓鱼,钓到的比较多吗?
一共是50+46+42+38+34+30+26+22+18=306条
但是如果用题解第一篇的动态规划算法,算出来的是298?这是怎么回事?有没有大佬解答一下?
顺便帮我看看我的代码为什么不行呗,306这个答案就是用我的代码算出来的
#include<iostream>
using namespace std;
int n,h;
int f[30],d[30],t[30],dp[30][200],flag[30][200];
int main(){
cin>>n>>h;
h=h*12;
for(int i=1;i<=n;i++)
cin>>f[i];
for(int i=1;i<=n;i++)
cin>>d[i];
for(int i=2;i<=n;i++){
cin>>t[i];
t[i]+=t[i-1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=h;j++){
int pos;
dp[i][j]=dp[i-1][j],pos=flag[i-1][j];
for(int k=1;k<=j;k++){
int times=max(0,k-(t[i]-t[flag[i-1][j-k]]));
if( d[i]!=0 )
times=min(times,f[i]/d[i]+1);
if( dp[i-1][j-k]+times*f[i]-d[i]*times*(times-1)/2>=dp[i][j] )
dp[i][j]=dp[i-1][j-k]+times*f[i]-d[i]*times*(times-1)/2,pos=i;
}
flag[i][j]=pos;
}
}
cout<<dp[n][h];
return 0;
}