2020 Multi-University Training Contest 3---- HDU--6800、Play osu! on Your Tablet （数据结构优化dp）

题目链接

题面：

题意：
你需要按照给定的顺序点击 $n$n 个点，每个点都有他的坐标。
有两只手指可以用，某个点被其中任意一只手指点击即可。

每只手指第一次点击不需要花费，第一次之后每次点击的花费等于当前点击的点和上一个点击的点的曼哈顿距离。问你点击完所有点的最小花费。

题解：
我们设 $dis(i,j)$dis(i,j) 为第 $i$i 个点到第 $j$j 个点的曼哈顿距离。
设 $dp\left[i\right]\left[j\right]$dp[i][j] 为点击了前 $i$i 个点且一根手指放在第 $i$i 个点，另一根手指放在第 $j$j 个点的最小代价。
初始时， $dp\left[1\right]\left[j\right]=0$dp[1][j]=0，表示两根手指的起始位置分别是第 $i$i 个点和第 $j$j 个点。

考虑转移：
$dp[i+1]\left[j\right]=min\left(dp\right[i+1\left]\right[j],dp[i\left]\right[j]+dis(i,i+1\left)\right)$dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis(i,i+1)) 表示手指从第 $i$i 个点到第 $i+1$i+1 个点。
$dp[i+1]\left[i\right]=min\left(dp\right[i+1\left]\right[i],dp[i\left]\right[j]+dis(j,i+1\left)\right)$dp[i+1][i]=min(dp[i+1][i],dp[i][j]+dis(j,i+1)) 表示手指从第 $j$j 个点到第 $i+1$i+1 个点。

注意到第一种转移相当于给每个 $j$j 对应的信息增加定值，第二种转移相当于对所有 $j$j 求出信息最小值后对单个 $dp$dp 值进行更新，这启发我们使用数据结构维护信息。

我们设 $f\left[i\right]\left[j\right]=dp\left[i\right]\left[j\right]-{\sum }_{k=1}^{i-1}dis(k,k+1)$f[i][j]=dp[i][j]−k=1∑i−1​dis(k,k+1)

则转移变为以下两个：
①、 $f[i+1]\left[j\right]=min\left(f\right[i+1\left]\right[j],f[i\left]\right[j\left]\right)$f[i+1][j]=min(f[i+1][j],f[i][j])

$f[i+1]\left[j\right]=dp[i+1]\left[j\right]-{\sum }_{k=1}^{i}dis(k,k+1)=dp\left[i\right]\left[j\right]+dis(i,i+1)-{\sum }_{k=1}^{i}dis(k,k+1)=dp\left[i\right]\left[j\right]-{\sum }_{k=1}^{i-1}dis(k,k+1)=f\left[i\right]\left[j\right]$f[i+1][j]=dp[i+1][j]−k=1∑i​dis(k,k+1)=dp[i][j]+dis(i,i+1)−k=1∑i​dis(k,k+1)=dp[i][j]−k=1∑i−1​dis(k,k+1)=f[i][j]

②、 $f[i+1]\left[i\right]=min\left(f\right[i+1\left]\right[j],f[i\left]\right[j]+dis(j,i+1)-dis(i,i+1\left)\right)$f[i+1][i]=min(f[i+1][j],f[i][j]+dis(j,i+1)−dis(i,i+1))

$f[i+1]\left[i\right]=dp[i+1]\left[i\right]-{\sum }_{k=1}^{i}dis(k,k+1)=dp\left[i\right]\left[j\right]+dis(j,i+1)-{\sum }_{k=1}^{i}dis(k,k+1)=dp\left[i\right]\left[j\right]-{\sum }_{k=1}^{i-1}dis(k,k+1)+dis(j,i+1)-dis(i,i+1)=f\left[i\right]\left[j\right]+dis(j,i+1)-dis(i,i+1)$f[i+1][i]=dp[i+1][i]−k=1∑i​dis(k,k+1)=dp[i][j]+dis(j,i+1)−k=1∑i​dis(k,k+1)=dp[i][j]−k=1∑i−1​dis(k,k+1)+dis(j,i+1)−dis(i,i+1)=f[i][j]+dis(j,i+1)−dis(i,i+1)

我们将上两式写成等式。
（1） $f[i+1]\left[j\right]=f\left[i\right]\left[j\right]$f[i+1][j]=f[i][j]
（2） $f[i+1]\left[i\right]=min\left(f\right[i\left]\right[j]+dis(j,i+1)-dis(i,i+1\left)\right)$f[i+1][i]=min(f[i][j]+dis(j,i+1)−dis(i,i+1))

对于上式中的 $i,j$i,j 均满足 j<i，因为最后一下点击在 $i$i，另一下点击不可能在 $i$i，且一定在 $i$i 之前。
假设我们已经求得 $f\left[n\right]\left[j\right]$f[n][j] 那么 $ans=min\left(f\right[n\left]\right[j\left]\right)+{\sum }_{k=1}^{n-1}dis(k,k+1)$ans=min(f[n][j])+k=1∑n−1​dis(k,k+1)

考虑怎么求解 $f$f。
我们发现可以枚举第一维 $i$i,只维护第二维 $j$j。
考虑 $f[i+1]\left[j\right]$f[i+1][j] 对于所有的 j<i 均可以由 $f\left[i\right]\left[j\right]$f[i][j] 转移而来。即这一部分可以不用动。
唯一新增的状态就是 $f[i+1]\left[i\right]$f[i+1][i]。

$f[i+1]\left[i\right]=min\left(f\right[i\left]\right[j]+dis(j,i+1)-dis(i,i+1\left)\right)$f[i+1][i]=min(f[i][j]+dis(j,i+1)−dis(i,i+1)) 其中 $dis(i,i+1)$dis(i,i+1) 是定值，单独计算。
即求解 $min\left(f\right[i\left]\right[j]+dis(j,i+1\left)\right)$min(f[i][j]+dis(j,i+1))

我们将 $\left(f\right[i\left]\right[j]+dis(j,i+1\left)\right)$(f[i][j]+dis(j,i+1))，看作一个三维坐标点 $\left(x\right[j],y[j],f[i\left]\right[j\left]\right)$(x[j],y[j],f[i][j])。

那么当前要求解 $\left(x\right[i+1],y[i+1],0)$(x[i+1],y[i+1],0) 与 j<i 的所有的三维坐标点的最小距离。
这个距离定义为 前两维为曼哈顿距离，第三维为 $f\left[i\right]\left[j\right]$f[i][j] 的值。

假设这个最小值为 $ans$ans，那么再将 $\left(x\right[i],y[i],ans-dis(i,i+1\left)\right)$(x[i],y[i],ans−dis(i,i+1)) 保存为一个已知的三维坐标点即可。

这里有一种特殊情况需要处理一下，就是 $ans\le 0$ans≤0 恒成立，所以求解出的 $ans$ans 要对 $0$0 取个 $min$min。
这是因为 $f[i+1]\left[i\right]$f[i+1][i] 有可能由 $f\left[i\right]\left[0\right]$f[i][0] 转移过来，此时 $f\left[i\right]\left[j\right]+dis(j,i+1)=0$f[i][j]+dis(j,i+1)=0
因为此时 $dis(j,i+1)=0$dis(j,i+1)=0（第一次动第二根手指） 且 $f\left[i\right]\left[j\right]=f\left[i\right]\left[0\right]=dp\left[i\right]\left[0\right]-{\sum }_{k=1}^{i-1}dis(k,k+1)=0$f[i][j]=f[i][0]=dp[i][0]−k=1∑i−1​dis(k,k+1)=0

可以维护这个问题的数据结构有很多（题解上说很多），而且还可以离线用分治解决。

这里选择用 kd-tree 来维护某个点到前面已知点的最短距离。
因为这个最短距离的特殊性，我们需要改动一些东西。

人丑常数大的 kd-tree。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=30;

struct Point
{
    ll x[3];
}po[maxn],p[maxn];

struct node
{
    ll p[3];
    int lc,rc;
    ll mi[3],ma[3];
    int si;
    void init(void)
    {
        lc=rc=si=0;
        mi[0]=mi[1]=mi[2]=0;
        ma[0]=ma[1]=ma[2]=0;
    }
}t[maxn];

int root,cnt,sum,now_maxx=3;
//root kd-tree 的根
//cnt kd-tree 节点编号
//sum 重构节点编号
//now_maxx 维度

ll res[3];//查询节点
ll in[3]; //插入节点
ll ans;   //最优答案
int hui[maxn],top;//回收节点
int nowd;  // 第几维
int dd,*pp;//重构

bool cmp(const Point &a,const Point &b)
{
    return a.x[nowd]<b.x[nowd];
}

bool balance(int q)
{
    return (double)t[t[q].lc].si<=t[q].si*alpha&&(double)t[t[q].rc].si<=t[q].si*alpha;
}

int newnode(int k=0)
{
    int p=0;
    if(top) p=hui[top--];
    else p=++cnt;
    t[p].si=t[p].lc=t[p].rc=0;
    //k=0 insert 插入
    //k!=0 rebuild 插入
    for(int i=0;i<now_maxx;i++)
        t[p].mi[i]=t[p].ma[i]=t[p].p[i]=(k==0?in[i]:po[k].x[i]);

    return p;
}

void  pushup(int p)
{
    int lc=t[p].lc,rc=t[p].rc;
    for(int i=0;i<now_maxx;i++)
    {
        if(lc) t[p].mi[i]=min(t[p].mi[i],t[lc].mi[i]),t[p].ma[i]=max(t[p].ma[i],t[lc].ma[i]);
        if(rc) t[p].mi[i]=min(t[p].mi[i],t[rc].mi[i]),t[p].ma[i]=max(t[p].ma[i],t[rc].ma[i]);
    }
    t[p].si=t[lc].si+t[rc].si+1;
}


int build(int l,int r,int d)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    nowd=d;
    nth_element(po+l,po+mid,po+r+1,cmp);
    int p=newnode(mid);
    t[p].lc=build(l,mid-1,(d+1)%now_maxx);
    t[p].rc=build(mid+1,r,(d+1)%now_maxx);
    pushup(p);
    return p;
}

void _insert(int &p,int d)
{
    if(!p)
    {
        pp=NULL;
        p=newnode();
        return ;
    }
    if(in[d]<t[p].p[d])
        _insert(t[p].lc,(d+1)%now_maxx);
    else _insert(t[p].rc,(d+1)%now_maxx);
    pushup(p);
    if(!balance(p)) pp=&p,dd=d;
}


void dfs(int p)
{
    if(t[p].lc) dfs(t[p].lc);
    ++sum;
    for(int i=0;i<now_maxx;i++)
        po[sum].x[i]=t[p].p[i];
    hui[++top]=p;
    if(t[p].rc) dfs(t[p].rc);
}

void rebuild(void)
{
    sum=0;
    dfs(*pp);
    (*pp)=build(1,sum,dd);
}

void _insert(void)
{
    _insert(root,0);
    if(pp!=NULL) rebuild();
}

//这个题的dis有点特殊
//第1维和第2维是曼哈顿距离，第3维是直接加第3维的权值
inline ll dis(int p)
{
    ll ans=0;
    for(int i=0;i<now_maxx-1;i++)
        ans+=1ll*abs(t[p].p[i]-res[i]);
    ans+=1ll*t[p].p[now_maxx-1];
    return ans;
}

//同样我们在某一棵子树上找最小值的时候
//前两维是曼哈顿距离，第3维是直接加第3维的权值
inline ll di(int p)
{
    ll ans=0;
    for(int i=0;i<now_maxx-1;i++)
        ans+=max(t[p].mi[i]-res[i],0)+max(res[i]-t[p].ma[i],0);
    ans+=t[p].mi[now_maxx-1];
    return ans;
}

void ask(int p)
{
    if(!p) return ;
    if(dis(p)<ans) ans=dis(p);
    ll dl=lnf,dr=lnf;
    if(t[p].lc) dl=di(t[p].lc);
    if(t[p].rc) dr=di(t[p].rc);
    if(dl<dr)
    {
        if(dl<ans)
            ask(t[p].lc);
        if(dr<ans)
            ask(t[p].rc);
    }
    else
    {
        if(dr<ans)
            ask(t[p].rc);
        if(dl<ans)
            ask(t[p].lc);
    }
}

void init(int n)
{
    root=0,sum=0,cnt=0;
    top=0;
    for(int i=1;i<=cnt;i++)
        t[i].init();
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n;
        scanf("%d",&n);
        ll sum=0;
        ll minn=lnf;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&p[i].x[0],&p[i].x[1]);
            if(i!=1)
                sum+=abs(p[i].x[0]-p[i-1].x[0])+abs(p[i].x[1]-p[i-1].x[1]);
        }

        if(n<=2)
        {
            printf("0\n");
            continue;
        }

        for(int i=2;i<=n;i++)
        {
            res[0]=p[i].x[0],res[1]=p[i].x[1],res[2]=0;

            ans=lnf;
            ask(root);
            //考虑 f[i+1][i] 直接由 f[i][0] 转移过来，此时ans应为0
            //因为：
            //此时 dis(0,i+1) 是第二根手指的第一步，不需要计算
            //f[i][0]=dp[i][0]-sum_k_from_1_to_i-1 dis(k,k+1)
            //而dp[i][0]=sum_k_from_1_to_i-1 dis(k,k+1)
            ans=min(ans,0);
            ans=ans-(abs(p[i].x[0]-p[i-1].x[0])+abs(p[i].x[1]-p[i-1].x[1]));

            in[0]=p[i-1].x[0],in[1]=p[i-1].x[1],in[2]=ans;
            _insert();

            minn=min(minn,ans+sum);
        }
        printf("%lld\n",minn);
        init(n);
    }
    return 0;
}