洛谷P2893 [USACO08FEB]修路Making the Grade
这里有一个结论就是修改后的道路高度在原来的那些道路的高度中，出现过（修改后为了节省花费，肯定数字要尽量向那些没修改过的靠近，）所以我们把所有出现过的道路高度离散化，存在b数组中b[j]表示第j大的高度。我们用f[i][j]将前i段变作不下降序列，且第j段道路的高度为b[j]时的最小花费，显而易见，f[i][j]=min(f[i-1][k])+abs(a[i]-b[j])(1<=k<=j）其中a[i]表示第i段路原本的高度。然而如果枚举k的话，你会发现时间复杂度为n^3。为了解决这个问题，我们发现min(f[i-1][k])是可以在做第i-1段路段的时候处理出来的，（这个还是看代码吧。）所以复杂度就成了n^2。我表示懒得用滚动数组，所以开了二维。。。处理不上升序列的话和这个差不多。
1 #include2 #define For(i,j,k) for(int i=j;i<=k;i++) 3 #define LL long long 4 using namespace std ; 5 6 inline int read() 7 { 8 int x = 0 , f = 1 ; 9 char ch = getchar() ; 10 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 11 while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 12 return x * f ; 13 }14 15 const int N = 2011,inf = 1e9 ; 16 int n,ans ; 17 int a[N],b[N],f[N][N],minf[N][N] ; 18 19 inline void SWAP() 20 {21 For(i,1,n/2) swap(a[i],a[n-i+1]) ; 22 }23 24 inline void dp() 25 {26 For(i,1,n) minf[0][i] = 0 ; 27 For(i,1,n) 28 For(j,1,n) {29 f[i][j] = minf[i-1][j]+ abs( b[j]-a[i] ) ; 30 if(j!=1) minf[i][j] = min(f[i][j],minf[i][j-1]) ; 31 else minf[i][j] = f[i][j] ; 32 }33 For(i,1,n) 34 if( ans > f[n][i] ) ans = f[n][i] ; 35 }36 37 int main() 38 {39 n = read() ; 40 For(i,1,n) a[ i ] = read(),b[ i ] = a[ i ] ; 41 sort(b+1,b+n+1) ; 42 ans = inf ; 43 dp() ; SWAP() ; dp() ; 44 printf("%d\n",ans) ; 45 return 0 ; 46 }