233
题意：分析：代码：
题意：
给出一个序列
a
i
a_i
ai，当想要经过
i
∼
i
+
1
i\sim i+1
i∼i+1这段路时，花费为
∣
a
i
−
a
i
+
1
∣
|a_i-a_{i+1}|
∣ai−ai+1∣ 但我们可以选择任意相邻的位置进行交换
a
i
a_i
ai和
a
i
+
1
a_{i+1}
ai+1，只有一个限制，即每次交换的
a
i
、
a
i
+
1
a_i、a_{i+1}
ai、ai+1必须在上次交换的
a
k
、
a
k
+
1
a_k、a_{k+1}
ak、ak+1后，也就是
k
<
i
k<i
k<i 问花费和最少是多少
分析：
根据题目保证的交换条件，嗯，这很
d
p
dp
dp 其实想着
d
p
dp
dp，后来又想搞个贪心偷鸡，但正确性一下就锅了，却给我提供了一个很有用的结论 对于一个位置
i
i
i，要么往前一位，要么就往后任意位，然后
y
y
yy
yy一下交换的过程，可以发现，若设交换后的位置是
j
j
j，那花费真正产生变化的只有
i
−
1
∼
i
i-1\sim i
i−1∼i和
j
∼
j
+
1
j\sim j+1
j∼j+1，在这中间的
i
∼
j
i\sim j
i∼j是不会产生变化的，所以可以预处理下 设
f
i
,
j
f_{i,j}
fi,j表示
a
i
a_i
ai交换到了
a
j
a_j
aj的位置的最少花费，转移的时候记录下之前状态转移到第
i
i
i位的最小值，然后枚举之后的位置
j
j
j，设
s
i
,
j
s_{i,j}
si,j表示
i
∼
j
i\sim j
i∼j的花费，也就是之前预处理的那个东东，转移过去的花费就可以表示成
f
i
,
j
=
m
i
n
+
s
i
+
1
,
j
+
∣
a
j
−
a
i
∣
f_{i,j}=min+s_{i+1,j}+|a_j-a_i|
fi,j=min+si+1,j+∣aj−ai∣ 最后答案就去找交换到
n
n
n的上一次位置在哪里，取最小值
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#define LL long long
using namespace std
;
inline int read() {
int d
=0,f
=1;char s
=getchar();
while(s
<'0'||s
>'9'){if(s
=='-')f
=-1;s
=getchar();}
while(s
>='0'&&s
<='9'){d
=d
*10+s
-'0';s
=getchar();}
return d
*f
;
}
LL a
[2005],f
[2005][2005],s
[2005][2005];
int main()
{
LL n
=read();
for(LL i
=1;i
<=n
;i
++) a
[i
]=read();
for(LL i
=1;i
<n
;i
++) for(LL j
=i
+1;j
<=n
;j
++) s
[i
][j
]=s
[i
][j
-1]+abs(a
[j
]-a
[j
-1]);
memset(f
,0x3f,sizeof f
);
for(LL i
=1;i
<=n
;i
++) f
[1][i
]=s
[2][i
]+abs(a
[1]-a
[i
]);
for(LL i
=2;i
<=n
;i
++)
{
LL mx
=2147483647;
for(LL j
=1;j
<i
;j
++)
{
f
[i
][i
]=min(f
[i
][i
],f
[j
][i
-1]+abs(a
[i
]-a
[j
]));
mx
=min(mx
,f
[j
][i
-1]+abs(a
[i
+1]-a
[j
]));
}
for(LL j
=i
+1;j
<=n
;j
++) f
[i
][j
]=min(f
[i
][j
],mx
+s
[i
+1][j
]+abs(a
[i
]-a
[j
]));
}
LL ans
=2147483647;
for(LL i
=1;i
<=n
;i
++) ans
=min(ans
,f
[i
][n
]);
cout
<<ans
;
return 0;
}
