懒得弄题目了,题目应该很简洁了,不需要翻译,再让我翻译我可以翻的比题目更多
首先我们需要知道一个结论
一定存在一种最优解使得 B 中的每个数都在原序列中出现过
这个很简单我们可以用“反证法”证明,“反正”他就是正确的
正紧的,我们可以用数学归纳法证明
用什么方法不重要,但是这个思路倒是挺难想到的
其实我是认真证明了一边的的,但是因为没有保存www……
这玩意儿纯属抄LYD的,Y总说LYD数学不好,所以证明不是很清楚,建议大家去看一看Y总的题解 Y总的题解
这一部分证明完之后,剩下的就比较简单了。大致思路其实和LCIS差不多的。
我们设一个数组$f_{i,j}$表示已经处理好了前i个数,最后一个数为$B_i$=$A’_j$
($A’_j$为排序过的A序列)
那转移方程就比较简单了
状态计算:
依据倒数第二个数分配的是哪个A’[i]将f[i][j]所代表的集合划分成j个不重不漏的子集:
倒数第二个数选取的是A’[1]的所有方案的结合,最小值是 f[i - 1][1] + abs(A[i] - A’[j]);
倒数第二个数选取的是A’[2]的所有方案的结合,最小值是 f[i - 1][2] + abs(A[i] - A’[j]);
倒数第二个数选取的是A’[j]的所有方案的结合,最小值是 f[i - 1][j] + abs(A[i] - A’[j]);
f[i][j]在所有子集的最小值中取min即可。
最终答案需要遍历最后一个数的所有取值,然后取min即可。
同LCIS一样,用类似val的东西去去掉一个循环
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2010;
const int INF=0x3f3f3f3f;
int a[maxn],b[maxn];
int f[maxn][maxn],n;
int work(){
for(int i=1;i<=n;i++) b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++){
int val=INF;
for(int j=1;j<=n;j++){
val=min(f[i-1][j],val);
f[i][j]=val+abs(a[i]-b[j]);
}
}
int res=INF;
for(int i=1;i<=n;i++) res=min(res,f[n][i]);
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=work();
reverse(a+1,a+1+n);
int ans=min(res,work());
cout<<ans<<endl;
return 0;
}
非常感谢读者的阅读,本文latex的使用不够熟练,在某些论证上也不够清晰,希望读者谅解,有什么问题敬请指出