圣诞树-题解
Grow_
·
·
题解
区间 DP 的思路各位大佬已经讲得很清楚了，我就不多说了，但有几个点大佬们并没有讲，我来水篇题解给大家讲一下。
- 关于为什么交叉比不交叉更优的证明：
$\therefore DE+CE>CD,AE+BE>AB$。
$\therefore DE+CE+AE+BE>AB+CD$。
$\therefore BD+AC>AB+CD$。
$\therefore BD+AC+BC>AB+CD+BC$。
综上，走交叉的路一定比走不交叉的路路程长。
2. 如何根据结果来反推方案：
这个可能是蒟蒻们最关心的，但其实没有那么难。
我们只需要在每次计算完记录一下当前最优的上一步是从哪里推过来的，储存在 last 数组中，最后只需要找到最小的答案，再一步一步往上推，在中途压入栈，最后输出即可。
3. DP 的初始值：
这不是讲 DP 初始值该赋什么，而是讲另一件事：
**double 型变量不可以使用 memset 初始化！！！**
我在这里调了好久(悲)。
注意：统计 $y$ 坐标时，maxx 的初始值一定要设为 $-10^9$ ，否则就 90，本人就在这里卡了好几个小时（可能是我太蒟了）：
[90分记录](https://www.luogu.com.cn/record/117441489)&&
[AC记录](https://www.luogu.com.cn/record/117441884)。
附上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r,id;
}last[2005][2005][2];
int n,id,al,bl,fl;
double x[2005],y[2005],maxn=-1e9,dp[2005][2005][2],ans = 1e9;//maxn一定记得设成-1e9！！！
double wok(int i,int j){
double a = pow((x[i]-x[j]),2);
double b = pow((y[i]-y[j]),2);
return sqrt(a+b);
}//计算两点之间的距离
signed main(){
cin >> n;
for(int i = 1;i<=n;i++){
cin >> x[i] >> y[i];
if(maxn<y[i]){
maxn=y[i];
id = i;
}
//求y坐标最大值
}
for(int i = 1;i<=n*2;i++){
for(int j = i;j<=n*2;j++){
dp[i][j][0]=dp[i][j][1]=1e9;//初始化，一定不要用memset!!!
}
}
dp[id][id][0]=dp[id][id][1]=0;
dp[id+n][id+n][0]=dp[id+n][id+n][1]=0;//对最高点进行初始化
for(int i = 1;i<=n;i++)x[i+n]=x[i],y[i+n]=y[i];//序列倍增
for(int len = 2;len<=n;len++){
for(int i = 1;i+len-1<=n*2;i++){
int j = i+len-1;
double a = dp[i+1][j][0]+wok(i,i+1);
double b = dp[i+1][j][1]+wok(i,j);
if(a>b)dp[i][j][0]=b,last[i][j][0].l=i+1,last[i][j][0].r=j,last[i][j][0].id=1;
else dp[i][j][0]=a,last[i][j][0].l=i+1,last[i][j][0].r=j,last[i][j][0].id=0;
a = dp[i][j-1][1]+wok(j-1,j);
b = dp[i][j-1][0]+wok(i,j);
if(a>b)dp[i][j][1]=b,last[i][j][1].l=i,last[i][j][1].r=j-1,last[i][j][1].id=0;
else dp[i][j][1]=a,last[i][j][1].l=i,last[i][j][1].r=j-1,last[i][j][1].id=1;
//转移
}
}//求DP和last的值，其中last表示当前最优的上一步是从哪里推过来的
for(int i = 1;i+n-1<=n*2;i++){
int j = i+n-1;
if(ans>dp[i][j][1]){
al = i;
bl = j;
fl = 1;
ans = dp[i][j][1];
}
if(ans>dp[i][j][0]){
al = i;
bl = j;
fl = 0;
ans = dp[i][j][0];
}
}//寻找最小值的DP位置
stack<int>st;
if(fl == 1)st.push(bl%n);
else st.push(al%n);
for(int i = 1;i<n-1;i++){
int l = last[al][bl][fl].l;
int r = last[al][bl][fl].r;
int idd = last[al][bl][fl].id;
al = l;
bl = r;
fl = idd;
//更新当前位置
if(fl == 1)st.push(bl%n);
else st.push(al%n);
//将上一步的位置压入栈
}
cout << id << " ";
while(!st.empty()){
if(st.top()==0)cout << n << " ";
else cout << st.top() << " ";
//输出答案
st.pop();
//一定要pop，不然会死循环
}
return 0;
}
```