[春季测试] 圣诞树错题重做

前情提要

先赞后看，必成习惯

考试游寄：

好耶，一看就是最小生成树

然后luogu 85

啊？85还可以了，就这样吧

然后

发现路径搜索的距离打错了

本来应该是(y-yy)*(y-yy)的，打成了(yy-yy) *(y-yy)

题目描述

众所周知，3202 年的圣诞节快要到了，因此小 Ω 买了一棵圣诞树和一根挂满了彩灯的电线，并打算把这根电线缠绕在圣诞树上。

圣诞树可以视作一个二维平面上有 $n$ 个顶点的凸多边形。这 $n$ 个顶点可以用于固定电线，且按逆时针顺序依次编号为 $1, \cdots, n$。其中第 $i$ 个顶点的坐标为 $(x_i, y_i)$，记其中 $y$ 坐标最大的顶点的编号为 $k$（若有多个满足条件的顶点，则取编号最小的）。不保证编号为 $1$ 的顶点的 $x$ 坐标最小。

下图左侧展示了一棵圣诞树的轮廓，其中 $y$ 坐标最大的顶点的编号为 $k = 5$。

图 2：一棵圣诞树及一种可能的挂电线的方案

小 Ω 希望用挂满了彩灯的电线装饰这棵圣诞树。出于美观性考虑，她希望这根电线经过所有顶点恰好一次；为了连接电源，这根电线需要从 $(x_k, y_k)$ 出发。形式化地，她需要决定一个 $1, \cdots, n$ 的排列 $p_1, \cdots, p_n$，满足 $p_1 = k$，随后这根电线从 $(x_{p_1}, y_{p_1})$ 出发，依次经过 $(x_{p_2}, y_{p_2}), \cdots, (x_{p_n}, y_{p_n})$。此时，电线长度为 $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$。

其中 $\operatorname{d}$ 为平面上的欧几里得距离，即 $\operatorname{d}((x, y), (x', y')) = \sqrt{(x - x')^2 + (y - y')^2}$。

上图右侧展示了一种可能的方案，此时对应的排列为 $5, 4, 8, 6, 3, 9, 1, 7, 2$。

为了节省成本，她希望你能在所有可能的方案中，给出一种使电线长度最短的方案。如果使电线长度最短的方案不唯一，你只需要求出其中任意一种。

考虑到浮点数产生的误差，你输出的方案与最优方案的线段长度的相对误差或绝对误差不超过 $10^{-10}$ 时即认为答案正确。

输入格式

第一行包含一个正整数 $n$，表示圣诞树的顶点数。

接下来 $n$ 行，其中第 $i$ 行包含两个精确到小数点后 $9$ 位的实数 $x_i, y_i$ 表示编号为 $i$ 的顶点的坐标。

数据保证这 $n$ 个点两两不同，并且依次连接 $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$ 将形成一个凸多边形。

输出格式

输出一行包含 $n$ 个由单个空格隔开的正整数 $p_1, p_2, \cdots, p_n$，表示一个 $1, \cdots, n$ 的排列，满足 $p_1 = k$，且电线的长度 $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$ 在所有可能的方案中最短。如果这样的方案不唯一，请输出其中任意一种方案。

样例 #1

样例输入 #1

3
0.000000000 0.000000000
3.000000000 0.000000000
1.000000000 1.000000000

样例输出 #1

3 1 2

提示

【样例 1 解释】

这一样例中只有下图所示的两种方案，对应排列分别为 $3, 1, 2$ 或 $3, 2, 1$，电线长度分别为 $3 + \sqrt{2}$ 和 $3 + \sqrt{5}$，而 $3 + \sqrt{2} < 3 + \sqrt{5}$。

因此答案对应的排列为 $3, 1, 2$。

图 3：样例 1 的全部两种可能的方案

【数据范围】

对于所有数据，保证 $3 \le n \le 1000$；$|x_i|, |y_i| \le 10^7$。

测试点编号	$n \le$	特殊性质
1, 2	$4$	无
3, 4, 5, 6	$9$	无
7, 8, 9, 10, 11, 12	$18$	无
13, 14	$10^3$	A
15, 16	$10^3$	B
17, 18, 19, 20	$10^3$	无

特殊性质 A：保证存在正整数 $m \ge n$，使得输入的 $n$ 个顶点对应正 $m$ 边形中连续的一段顶点。

特殊性质 B：保证 $x_1 < x_2 < \cdots < x_n$，且 $y_1 > y_2 > \cdots > y_n$。

本题思路

前提条件和思路引导

为了方便讲解，讲点命名为1,2,3,t,5,67,，其中t为最高点

结论1：这里面的线段（最优解）不可能交叉

结论1证明：如果交叉了，那么我肯定能找到一条路线，让长度更短，并且出发点和结束点是仍然相同的，而且用的替换的点不会是还没有连接的点（不会干扰其他）

至于这个，可以自己画个五边形感受一下

有了结论1，就可以发现，这道题的区间是不断“左右延伸的”，也就是说用的点的都是紧挨着的，于是就可以套用区间dp的模板了

而这个模板，正是一个典型，看模板题-P1220 关路灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间dp(详见另一博客)

重难点

本题不同于其他区间dp的难点如下

第一，这是个更高级的模板题，详见上文P1220关路灯

第二，这个需要保证t作为定点，不能使用两次

其实解决方法很简单，命令dp[t] [t] [0]/dp[t] [t] [1]=0;即可

第三，这个还是在环上的一个dp

解决还是很简单，复制一次就完了，但是注意不能复制过t

例如1,2,3,t,4,5

复制后应该是

1,2,3,t,4,5,1,2,3;

第四，那么加入了新的点dp该怎么找两点之间的距离呢（毕竟是新建点）

我是记录了原始点的id与原始点间的距离，然后把原始点的id给相应的新的点

虽然我会用新的点进行dp，但是我用点的id来看两点间的距离

这也会在最后dfsprint中有效果

接着，dp的长度也是有限制的：必须为n，同时也必须要过t点

但其实像上面那样复制后就不必担心此问题了

最后便是答案的输出，当枚举完所有的dp后，因为我们已经知道每一个dp了，所以也很容易知道他是从哪里转移过来的

于是记录最后的l,r,op，再给他dfs一遍，dfs时输出就可以啦

那么献上代码

#include<bits/stdc++.h>
using namespace std;
string s;

double dp[2055][2055][2];
double mp[2055][2055];
int n,sid;
struct node{
    int id;
    double x;
    double y;
}dot[2005];
double dis(double x,double y,double xx,double yy){
    return (double)sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
double dfs(int x,int y,bool op){
    if(dp[x][y][op]!=-1){
		return dp[x][y][op];
	}
	if(x>y){
		dp[x][y][op]=1ll<<60;
		return 1ll<<60;
	}
	if(x==y){
        if(x==sid){
            dp[x][x][op]=0;
        }
        else dp[x][x][op]=1ll<<60;
        return dp[x][x][op];
	}

	dp[x][y][op]=1ll<<60;
    if(op) dp[x][y][op]=min(dfs(x,y-1,0)+mp[dot[y].id][dot[x].id],dfs(x,y-1,1)+mp[dot[y].id][dot[y-1].id]);
    else dp[x][y][op]=min(dfs(x+1,y,0)+mp[dot[x+1].id][dot[x].id],dfs(x+1,y,1)+mp[dot[y].id][dot[x].id]);
	return dp[x][y][op];
}
void printdfs(int x,int y,int op){
    if(x==y&&y==sid){
        cout<<dot[x].id<<" ";
        return;
    }
    if(op){
        if(dp[x][y-1][0]+mp[dot[y].id][dot[x].id]<dp[x][y-1][1]+mp[dot[y].id][dot[y-1].id]){
            printdfs(x,y-1,0);
            cout<<dot[y].id<<" ";
        }
        else{
            printdfs(x,y-1,1);
            cout<<dot[y].id<<" ";
        }
    }
    else{
        if(dfs(x+1,y,0)+mp[dot[x+1].id][dot[x].id]<dfs(x+1,y,1)+mp[dot[y].id][dot[x].id]){//突然发现我已经记忆化搜索了，打dfs和dp效果一样
            printdfs(x+1,y,0);
            cout<<dot[x].id<<" ";
        }
        else{
            printdfs(x+1,y,1);
            cout<<dot[x].id<<" ";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    double maxy=-INT_MAX;
    cin >> n ;
    for(int i=1;i<=n;i++){
        cin >> dot[i].x>>dot[i].y;
        dot[i].id=i;
        dot[i+n]=dot[i];
        if(maxy<dot[i].y){
            maxy=dot[i].y;
            sid=i;
        }
        for(int j=1;j<=i-1;j++){
            mp[j][i]=mp[i][j]=dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
        }
    }

    for(int i=1;i<=n+n;i++){
        for(int j=1;j<=n+n;j++){
            for(int op=0;op<=1;op++){
                dp[i][j][op]=-1;
            }
        }
    }
    dp[sid][sid][0]=dp[sid][sid][1]=0;
    double ans=1ll<<60;
    int lasl,lasr,lasf;
    for(int i=1;i<=sid;i++){
       // cout<<dfs(i,i+n-1,0)<<" "<<dfs(i,i+n-1,1)<<endl;
        if(ans>dfs(i,i+n-1,0)){
            ans=dfs(i,i+n-1,0);
            lasl=i;
            lasr=i+n-1;
            lasf=0;
        }
        if(ans>dfs(i,i+n-1,1)){
            ans=dfs(i,i+n-1,1);
            lasl=i;
            lasr=i+n-1;
            lasf=1;
        }
    }
    //cout<<ans<<" "<<lasl<<" "<<lasr<<" "<<lasf;
    printdfs(lasl,lasr,lasf);


}

都到这里了？不点个赞再跑？