Final Dash
日常更新
审题
传送门
首先要明确，我们的最优解是不可能把同一个数字转换两次的（很好想）
然后，奇怪的思路就来了：
既然我们可以一次把它移到正确的位置上，那么这个数字就可以理解为直接被移走了。
所以……
做法
题目被我们转化成了：删除几个数字，使得数列单调递增，所求的是移走数字的最小和。 使得删除的和最小，就意味着留下的和最大。
那么问题就变成了：保留几个单调递增的数字，使得和最大。
那就简单很多了。
程序代码
最长不降子序列变形
F[i]=max(a[i], f[j]+a[i])其中，j<i`a[j]<=a[i]`
f[i]表示以a[i]结尾的的不降序列的和的最大值；
初始值：f[i]=a[i]
结果：max(f[i])即最优的序列以任意数结尾都有可能。
int T,n,a[N],f[M];
int sum,ans;
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--){
cin>>n; sum=ans=0;
for(int i=1; i<=n; i++){
cin>>a[i]; sum+=a[i];
f[i]=a[i];
}
for(int i=1; i<=n; i++)
for(int k=1; k<i; k++)
if(a[i]>=a[k]) f[i]=max(f[i],f[k]+a[i]);
for(int i=1; i<=n; i++) ans=max(ans,f[i]);
cout<<sum-ans<<endl;
}
return 0;
}
|
