Steven_MengのBlog

传送门

我们yy一下,一个数不可能被移动超过$2$次,否则就不是最优解,我们可以这么想,移动之后的序列一定是有序的,也就是说它是固定的,问题就转化为钦定几个单调递增的数的位置,它们不移动,移动其它的数,使序列变得有序。

既然要让移动的数的总和尽量小,那就要让没有移动的数的总和尽量大,问题就转化为求序列的和最大的上升子序列,$dp$$O(n^2)$求一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define MAXN 105
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],dp[MAXN];
int main(){
int t=read();
while (t--){
int n=read(),sum=0;
for (register int i=1;i<=n;++i){
a[i]=read();
sum+=a[i];
}
memset(dp,0,sizeof(dp));
int maxn=0;
for (register int i=1;i<=n;++i){
for (register int j=1;j<i;++j){
if (a[j]<=a[i]){
dp[i]=max(dp[i],dp[j]);
}
}
dp[i]+=a[i];
maxn=max(dp[i],maxn);
}
printf("%d\n",sum-maxn);
}
}

 评论