wa on test 7 警示后人
  • 板块CF704B Ant Man
  • 楼主Mo默Sh笙
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/15 14:53
  • 上次更新2023/11/15 17:17:50
查看原帖
wa on test 7 警示后人
189485
Mo默Sh笙楼主2023/11/15 14:53

当 i!=s&&i!=e 时,对于新插入的点新开一段使得左右都比它大需要满足 j>(i>s)+(i>e) 的条件,即:

if(j>(i>s)+(i>e)) dp[i][j]=min(dp[i][j],dp[i-1][j-1]-x[i]+b[i]-x[i]+d[i]);//新开一段:左右都比它大 

因为 ss 和 ee 点都存在时,如果由 dp[i-1][j-1],j=2 转移过来则说明 ss 和 ee 被连成了同一段,这种情况下显然无法插入下一个点


附上这一段的填表法DP代码:

if(j>(i>s)+(i>e)) dp[i][j]=min(dp[i][j],dp[i-1][j-1]-x[i]+b[i]-x[i]+d[i]);//新开一段:左右都比它大 
dp[i][j]=min(dp[i][j],dp[i-1][j+1]+x[i]+a[i]+x[i]+c[i]);//合并两段:左右都比它小 
if(j>1||i<s) dp[i][j]=min(dp[i][j],dp[i-1][j]-x[i]+b[i]+x[i]+c[i]);//接在一段左:左比它大,右比它小 
if(j>1||i<e) dp[i][j]=min(dp[i][j],dp[i-1][j]+x[i]+a[i]-x[i]+d[i]);//接在一段右:左比它小,右比它大 	
2023/11/15 14:53
加载中...