动态规划、最长上升子序列类问题

看到云南省选有胆把看都看不懂的题面喂给选手，宁夏办省选的希望似乎更大了。

写题面的人麻麻趋势。

题意是给定一个长度为 $n$ 的序列，使用以下操作将序列排序，最小化代价。

• 选定序列中的元素 $a_i$，花费 $a_i$ 代价将其移动到任意位置。此后 $a_i$ 不能被选择。

$1 \leq n \leq 200$，$-10^7 \leq a_i \leq 10^7$

可以发现最终没有被选择过的数字形成一个不降子序列。

动态规划，设计 $dp_i$ 为以 $a_i$ 结尾的数字和最大的不降子序列的数字和，答案为

$$\sum\limits_{i=1}^{n} a_i - \max( \max\limits_{i=1}^{n} dp_i,0)$$

时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[205],dp[205];
void solution(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) dp[i]=a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i-1;j++) if(a[i]>=a[j]) dp[i]=max(dp[i],a[i]+dp[j]);
    ans=accumulate(a+1,a+n+1,0)-max(*max_element(dp+1,dp+n+1),0);
    printf("%d\n",ans);
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}