请求撤下题解
查看原帖
请求撤下题解
223100
xyz105楼主2024/10/15 20:28

该题解 提到如下状态转移方程: dpi,j=min(dpi1,j+1,minai2<ak,k<i{dpk,j1})dp_{i,j}=\min(dp_{i-1,j}+1,\min\limits_{\frac{a_i}{2}<a_k,k<i}\{dp_{k,j-1}\}) 该方程是错误的,正确的方程应为 dpi,j=min(dpi1,j+1,minai2<ak,ki{dpk1,j1})dp_{i,j}=\min(dp_{i-1,j}+1,\min\limits_{\frac{a_i}{2}<a_k,k\le i}\{dp_{k-1,j-1}\}) 题解代码也是这么写的:

dp[i][j]=dp[i-1][j]+1;
int last=upper_bound(a+1,a+i+1,a[i]/2)-a-1;
if(j>0)dp[i][j]=min(dp[i][j],dp[last][j-1]);

故该题解存在细节笔误。建议撤下该题解,以避免更多想要知道正解的人看到这篇题解而走了弯路。

2024/10/15 20:28
加载中...