gpt4 book ai didi

c++ - spoj 对待奶牛 DP 得到错误的答案?

转载 作者:太空宇宙 更新时间:2023-11-04 03:49:19 25 4
gpt4 key购买 nike

为什么我得到错误的答案。我使用了 DP 并将表格自下而上填充。

http://www.spoj.com/problems/TRT/

for(int i=0;i<n;i++)
{
dp[i][i]=n*a[i];
}

for(int i=n-2;i>=0;i--)
{
for(int j=i+1;j<n;j++)
{
dp[i][j]=max((i+1)*a[i]+dp[i+1][j],dp[i][j-1]+(i+1)*a[j]);//(i+1) is the age

}
}
printf("%d\n",dp[0][n-1]);

最佳答案

年龄不会是i+1。它将是 n+i-j。

dp[i][j] = max(  (n+i-j)*a[i]+dp[i+1][j],  dp[i][j-1] + (n+i-j)*a[j] );

关于c++ - spoj 对待奶牛 DP 得到错误的答案?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21954755/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com