题解：P12585 「KTSC 2019 R1」广播站

alexdai · 2026-10-22 13:59:57 · 题解

很容易发现最后路径不会从某个区间中出去再回来。

考虑区间 dp，首先给出很 naive 的 n^4 的状态定义：

• 转移考虑枚举左侧区间划分情况+右侧区间划分情况

容易注意到区间被 u 分开后左右两侧的划分方案没有任何的影响，所以简化状态至 f[h][u][i]，即区间 [i,u]（或者是 [u,i]）中所有点，在 h 步内走到 i 的最小代价

• 考虑 j\leq i 部分的转移，枚举 j: i-1 \to 1
  • 分类讨论 1：对于 f[h-1][j][i_2] 满足 j \leq i_2 的部分，将其与 f[h][u][i_2+1]，即 f[h][u][i_2+1]+f[h-1][j][i_2]+|x_j-x_u|^2 \to f[h][i][j]
  • 分类讨论 2：对于 f[h-1][j][i_2] 满足 j > i_2 的部分，将其与 f[h][i][j] 钦定选择了 j 的部分合并（记作 w = \max\{f[h][u][i_2+1]+f[h-1][j][i_2]+|x_j-x_u|^2\}），即主动转移方程为 w+f[h-1][j][i_2] \to f[h][i][i_2]

::::info[代码]

#include<bits/stdc++.h>
#include"stations.h"
void stations(std::vector<int> X);
void answer(std::vector<long long> Ans);
using namespace std;
#define ll long long
const int N=125;
ll f[N][N][N],x[N],dis[N][N];int n;

void test(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            dis[i][j]=dis[j][i]=(x[i]-x[j])*(x[i]-x[j]);
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)f[0][i][i]=0;
    vector<ll>Ans;
    for(int h=1,i,j,u;h<n;h++){
        ll w;
        for(i=1;i<=n;i++){
            f[h][i][i]=0;
            for(j=i-1;j>=1;j--){
                w=f[0][0][0];
                for(u=j;u<i;u++){
                    w=min(w,f[h][i][u+1]+f[h-1][j][u]);
                }f[h][i][j]=min(f[h][i][j],(w+=dis[j][i]));
                for(u=j-1;u>=1;u--){
                    f[h][i][u]=min(f[h][i][u],w+f[h-1][j][u]);
                }
            }
            for(j=i+1;j<=n;j++){
                w=f[0][0][0];
                for(u=i+1;u<=j;u++){
                    w=min(w,f[h][i][u-1]+f[h-1][j][u]);
                }
                f[h][i][j]=min(f[h][i][j],(w+=dis[j][i]));
                for(u=j+1;u<=n;u++){
                    f[h][i][u]=min(f[h][i][u],w+f[h-1][j][u]);
                }
            }
        }
        ll ans=f[0][0][0];
        for(i=1;i<=n;i++)ans=min(ans,f[h][i][1]+f[h][i][n]);
        Ans.push_back(ans);
    }
    answer(Ans);
}
void stations(vector<int>X){
    n=X.size();
    for(int i=0;i<n;i++)x[i+1]=X[i];
    test();
}

::::