题解：P12675 「LAOI-8」Boundary

· · 题解

考虑动态规划，设 dp_i 为赋值 [1,i] 的最小代价。

赋值 [j,i] 的代价为 \lvert a_i-a_j \rvert+i-j+1 ，所以

=i+1+\min_{1\le j<i} \left (\lvert a_i-a_j \rvert+dp_{j-1}-j \right )\end{aligned}

注意到在第二组测试数据中两个赋值后的区间之间也可以赋值，若第一个区间右端点为 k，第二个区间为 [j,i]，则代价为 \lvert a_i-a_j \rvert+i-j+1+j-k+1=\lvert a_i-a_j \rvert+i-k+2 ，所以

&=i+1+\min_{1\le k<j<i} \left (\lvert a_i-a_j \rvert+dp_{k}-k+1 \right )\\ &=i+1+\min_{1<j<i} \left (\lvert a_i-a_j \rvert+\min_{1\le k<j}(dp_{k}-k+1) \right ) \end{aligned}

令 minn_i=\min_{1\le j<i}(dp_i-i+1)，所以 dp_i=i+1+\min_{1<j<i} \left (\lvert a_i-a_j \rvert+minn_j \right )。

综上，可以得到

dp_i=i+1+\min_{1\le j<i} \left (\lvert a_i-a_j \rvert+\min(dp_{j-1}-j,minn_j) \right )\end{cases}\end{aligned}

拆掉绝对值得 dp_i=i+1+\min(\\ a_i+\min_{1\le j<i,a_j<a_i} \left (-a_j+\min(dp_{j-1}-j,minn_j) \right ),\\-a_i+\min_{1\le j<i,a_j>a_i} \left (a_j +\min(dp_{j-1}-j,minn_j) \right ))。

典型的二维偏序问题，可以用树状数组解决，时间复杂度 O(n\log n)。

参考程序：

#include<iostream>
#include<cstring>
const int N=1e6+10,INF=0x3f3f3f3f;
using namespace std;
int n;
int a[N],tr1[N],tr2[N],dp[N],minn[N];
int query(int x,int tr[]){
    int ans=INF;
    for(;x;x-=x&-x)ans=min(tr[x],ans);
    return ans;
}
void update(int x,int v,int tr[]){
    for(;x<=n;x+=x&-x)tr[x]=min(tr[x],v);
}
int main() {
    int t;
    for(cin>>t;t;--t){
        memset(tr1,INF,sizeof tr1);
        memset(tr2,INF,sizeof tr2);
        memset(minn,INF,sizeof minn);
        memset(dp,INF,sizeof dp);
        cin>>n;
        for(int i=1;i<=n;++i)scanf("%d",&a[i]);
        dp[0]=0;
        update(a[1],-a[1]-1,tr1);
        update(n-a[1]+1,a[1]-1,tr2);
        for(int i=2;i<=n;++i){
            dp[i]=i+1+min(a[i]+query(a[i],tr1),-a[i]+query(n-a[i]+1,tr2));
            minn[i]=min(minn[i-1],dp[i-1]+2-i);
            update(a[i],-a[i]+min(dp[i-1]-i,minn[i]),tr1);
            update(n-a[i]+1,a[i]+min(dp[i-1]-i,minn[i]),tr2);
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}