题意：给定长度为n（1<=n<=2000）的序列，将原序列变为单调不降或者单调不增的，求最小代价。
这儿的代价定义为：设新序列为c，代价=|a1-c1|+|a2-c2|+...+|an-cn|
这题看完题解也愣了好久，主要是状态设计的挺奇怪，而且一开始没弄懂怎么把3个循环优化成2个的
以单调不下降为例子（单调不增同理）。首先可以脑补，存在某种最优解序列，新序列中的数都是原序列中的数（严格证明鸽了......）
f[i][j]表示完成了前i个数的构造，且把第i个数ai变成第j小的数bj，所需要的最小代价。
那么有转移方程：f[i][j]=min(f[i-1][k])+abs(a[i]-b[j])，这儿数组b是a的升序排列（单调不降的情况），然后1<=k<=j（要保证把ai变成第j小的时候，构造的序列仍然单调不降）
看上去要用3重循环？但n<=2000复杂度就炸了。其实只要一边更新min(f[i-1][k])一般算当前的f[i][j]就行。
贴代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20+10;
bool cmp(int a,int b)
{
return a>b;
}
int a[maxn],b[maxn],f[maxn][maxn];
int n,i,j,k,t,ans1,ans2;
int dp()
{
int ans;
for (i=1;i<=n;i++) f[1][i]=abs(b[i]-a[1]);
for (i=2;i<=n;i++)
{
int mmin=1<<31-1;
for (j=1;j<=n;j++)
{
mmin=min(mmin,f[i-1][j]);
f[i][j]=mmin+abs(a[i]-b[j]);
}
}
ans=1<<31-1;
for (i=1;i<=n;i++) ans=min(ans,f[n][i]);
return ans;
}
int main()
{
cin>>n;
for (i=1;i<=n;i++)
{
cin>>a[i];b[i]=a[i];
}
sort(b+1,b+n+1);ans1=dp();
sort(b+1,b+n+1,cmp);ans2=dp();
cout<<min(ans1,ans2)<<endl;
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/12306923.html