P5414 [YNOI2019]排序

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

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

#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);
    }
}