@[czy0323](/user/538427) 我觉得可能是第一篇题解的dp代码有误,其他题解跑出来都是306。
by 颢颢 @ 2022-11-29 06:57:55
他代码 $ j$ 从 1 开始循环,会漏掉一些状态。我在他赋初值的地方将 $opt[1][0] $同样赋值为0,就输出了306
by 颢颢 @ 2022-11-29 07:02:30
@[颢颢](/user/289692) 哦哦,原来如此
by czy0323 @ 2022-11-29 21:23:18
1.题解第一篇的dp算法确实是错了的。~~但是我木有仔细看哪里错了~~
2.我的算法确实错了,错误也被我纠正了。想知道哪里错了的可以私我,~~不过也不会有人想知道吧,毕竟OIer一般都很忙~~
3.下面是我自己的AC代码,思路可能有点复杂,注意点也稍微较多,~~毕竟循环维数多~~
```cpp
#include<iostream>
using namespace std;
int n,h;
int f[30],d[30],T[30],dp[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++){ //前i个湖,并且一定经过第i个湖
for(int j=1;j<=h;j++){ //一共能钓鱼j分钟
for(int k=0;k<i;k++){ //由第k个湖中转
for(int t=T[i]+1;t<=j;t++){ //在第i个湖钓了t分钟的鱼
int times=t-T[i]; //剩下的钓鱼时间
if( d[i]!=0 )
times=min(times,f[i]/d[i]+1); //能用来钓鱼的时间
dp[i][j]=max(dp[i][j],dp[k][j-t+T[k]]+times*f[i]-d[i]*times*(times-1)/2);
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i][h]);
cout<<ans;
return 0;
}
```
综上所述,此贴正式宣告完结!
by czy0323 @ 2022-11-29 22:16:16