记录编号	584952	评测结果	AAAAAAAATT
题目名称	3937.[YNOI2019] 排序	最终得分	80
用户昵称	ムラサメ	是否通过	未通过
代码语言	C++	运行时间	2.065 s
提交时间	2023-11-17 14:21:36	内存使用	5.93 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,t,sum1,sum2;
ll a[100010],dp[100010];
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		sum1=0;
		sum2=0;
		cin>>n;
		for(ll i=1;i<=n;i++){
			cin>>a[i];
			sum1+=a[i];
			dp[i]=a[i];
		}
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<i;j++){
				if(a[i]>=a[j]){
					dp[i]=max(dp[i],dp[j]+a[i]);
				}
			}
		}
		for(ll i=1;i<=n;i++){
			sum2=max(dp[i],sum2);
		}
		cout<<sum1-sum2<<endl;
	}
	return 0;
}