P9119 [春季测试 2023] 圣诞树
题意是说:给你一个凸多边形,并且保证按照给你的点的顺序连起来一定是凸多边形,要求从最高点出发,访问全部点恰好一次的花费最小,其中任意两点之间的花费为两点间的欧几里得距离,最后依次输出访问的点的编号。
$n \le 1000;|x|,|y|\le 1e7 $
首先,这个题目保证按顺序连就是一个凸多边形,可以减轻不少麻烦,当时没看见想这个想了半天
那么我们就可以把这个顺序换一下,把最高点换成的编号换成n,其他跟着变一下,这样可以方便我们后边的计算,变换是简单的,最高点前一个点和最高点后一个点的方向一定是上下颠倒的,也就是说一个上来一个下去,并且他们的前一个数也一定和它的趋势是一样的,根据这一性质就转换完了。
这时考虑区间DP,由于n<=1000我们不能向其他区间DP一样从中间点转移过来,那么我们就让一个区间往外扩1，这样复杂度就是\(O(n^2)\)的，设\(f[l][r][0/1]\)表示对于转换过后的区间[l,r],我当前在区间的左端点(右端点)时的最小花费,这时我[l,r]的点都选过了,状态是好转移的,每次只要从我的前一个点转过来或者从我的另一个端点转过来,取min即可。至于最后要求的方案我每次取min成功后就记录一下我从哪过来的，最后递归输出就好了。那么这道题就结束了。
具体的转移是这样的
f[l][r][0]=f[l][r][1]=1e18;if(f[l][r][0]>f[l+1][r][0]+Calc(l,l+1))f[l][r][0]=f[l+1][r][0]+Calc(l,l+1),las[l][r][0]=0;if(f[l][r][0]>f[l+1][r][1]+Calc(l,r))f[l][r][0]=f[l+1][r][1]+Calc(l,r),las[l][r][0]=1;if(f[l][r][1]>f[l][r-1][0]+Calc(l,r))f[l][r][1]=f[l][r-1][0]+Calc(l,r),las[l][r][1]=0;if(f[l][r][1]>f[l][r-1][1]+Calc(r,r-1))f[l][r][1]=f[l][r-1][1]+Calc(r,r-1),las[l][r][1]=1;
最后的输出
void solve(int l,int r,int op){if(l==r) return printf("%d ",o[l].id),void();if(op) printf("%d ",o[r].id),solve(l,r-1,las[l][r][op]);else printf("%d ",o[l].id),solve(l+1,r,las[l][r][op]);
}
......
int main(){.......printf("%d ",o[n].id);solve(1,n-1,(f[1][n-1][0]+Calc(1,n)>f[1][n-1][1]+Calc(n-1,n)));return 0;
}
当然这一题还有一个性质，那就是连的边肯定不会有交叉，这样一定不优，这个可以通过三角形三边关系证明，但是用上面的做法是不用考虑这么多的，因为毕竟它本来就不优，我也不会选它，对转移也没什么影响，所以我也没在上面提到这一点。但是如果在分析上面的写法时用到了这个性质就不太合适了，既没有在你的代码里体现，又会让读者想太多不知道怎么写，既然不是同一种写法就不要混着讲。