正题
题目大意
n
n
n个地方，第
i
i
i个高度为
h
i
h_i
hi。每次可以交换一个
h
j
h_j
hj和
h
j
+
1
h_{j+1}
hj+1但是要满足操作的
j
j
j递增。
解题思路
也就是可以选择若干个区间，然后将区间的头部丢到尾部。
发现
d
p
dp
dp的瓶颈在于我们在枚举下一个时无法知道上一个的具体高度，但是我们处理一个位置
i
i
i时发现如果下一个位置作为区间的起点，那么下一个位置的高度就应该是
h
i
+
1
h_{i+1}
hi+1，否则就是
h
i
h_i
hi。
那么我们可以设
f
i
,
0
/
1
f_{i,0/1}
fi,0/1表示到第
i
i
i个，下一个是否作为区间的起点时的答案，然后就可以
O
(
n
2
)
O(n^2)
O(n2)转移了。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
const ll N
=2100;
ll n
,a
[N
],s
[N
],f
[N
][2];
int main()
{
scanf("%lld",&n
);
for(ll i
=1;i
<=n
;i
++){
scanf("%lld",&a
[i
]);
s
[i
]=s
[i
-1]+abs(a
[i
]-a
[i
-1]);
}
memset(f
,0x3f,sizeof(f
));
f
[0][0]=f
[0][1]=0;a
[0]=a
[1];
for(ll i
=1;i
<=n
;i
++){
for(ll j
=0;j
<i
-1;j
++){
if(i
==n
)f
[i
][0]=min(f
[i
][0],f
[j
][1]+s
[i
]-s
[j
+2]+abs(a
[i
]-a
[j
+1]));
else f
[i
][0]=min(f
[i
][0],f
[j
][1]+s
[i
]-s
[j
+2]+abs(a
[i
]-a
[j
+1])+abs(a
[j
+1]-a
[i
+1]));
f
[i
][1]=min(f
[i
][1],f
[j
][1]+s
[i
]-s
[j
+2]+abs(a
[i
]-a
[j
+1])+abs(a
[j
+1]-a
[i
+2]));
}
if(i
==n
)f
[i
][0]=min(f
[i
][0],f
[i
-1][0]);
else f
[i
][0]=min(f
[i
][0],f
[i
-1][0]+abs(a
[i
]-a
[i
+1]));
f
[i
][1]=min(f
[i
][1],f
[i
-1][0]+abs(a
[i
]-a
[i
+2]));
}
printf("%lld",f
[n
][0]);
}
