题目传送门：https://www.luogu.org/problem/P2893
本题系神奇的dp（这辈子都学不懂的玩意）。由于数据的 Ai 过大所以在其中进行排序处理，将它的下标作为它的大小（通俗离散化）。
我们用f[i][j]将前i段变作不下降序列，且第j段道路的高度为b[j]时的最小花费，显而易见。
dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]); （注：b[j]为离散化后第j个的大小）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 int ans=0x3f3f3f3f; 5 int a[2009]; 6 int b[2009]; 7 int dp[2009][2009];//dp[i][j] 8 inline long long read() 9 { 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 13 return x*f; 14 } 15 bool cmp(int a,int b) 16 { 17 return a>b; 18 } 19 int main() 20 { 21 n=read(); 22 for(int i=1;i<=n;i++) 23 a[i]=b[i]=read(); 24 for(int i=1;i<=n;i++)dp[i][0]=0x3f3f3f3f; 25 sort(b+1,b+1+n); 26 for(int i=1;i<=n;i++) 27 { 28 for(int j=1;j<=n;j++) 29 { 30 dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j])); 31 } 32 } 33 ans=dp[n][n]; 34 sort(b+1,b+1+n,cmp); 35 for(int i=1;i<=n;i++) 36 { 37 for(int j=1;j<=n;j++) 38 { 39 dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j])); 40 } 41 } 42 ans=min(ans,dp[n][n]); 43 cout<<ans; 44 }