专栏文章
题解：P12675 「LAOI-8」Boundary
P12675题解参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mip60n1v
- 此快照首次捕获于
- 2025/12/03 06:44 3 个月前
- 此快照最后确认于
- 2025/12/03 06:44 3 个月前
考虑动态规划，设 为赋值 的最小代价。
赋值 的代价为 ，所以
=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 $，所以
$$\begin{aligned} dp_i&=\min_{1\le k< j<i} \left (\lvert a_i-a_j \rvert+i-k+2+dp_{k} \right )\\
&=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 )$。
综上，可以得到
$$\begin{aligned}\begin{cases}dp_0=0\\
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)$。
参考程序：
```cpp
#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;
}
```相关推荐
评论
共 1 条评论，欢迎与作者交流。
正在加载评论...