题意大致就是求把一段序列改成单调递增或者单调递减最小费用,费用是改前改后的高度之差的绝对值。那就直接用dp去做。我们用dp[i][j]表示把前i段维护成有序的,第i段高度为h[j]时的最小花费。因为我们无论怎么改,其实改后的高度总是出现在原有序列之间的,因为显然改一个那改后的值一定与其左右两边的较小值相平。所以我们把高度离散化得到一个h数组。那么转移方程显然就是:
dp[i][j] = min(dp[i][k]) + abs(a[i] - h[j]);
而我们如果直接暴力枚举所有的k,复杂度为n3,显然会爆炸。考虑优化。我们其实不必枚举k,可以直接在前一次转移时求出最小的dp[i][k],具体细节看代码:
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<cstdlib> #include<ctime> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<deque> #define ll long long #define N 2010 using namespace std; int n,cnt; int dp[N][N]; int a[N],h[N]; int main() { scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d",&a[i]); h[i] = a[i]; } sort(h + 1,h + n + 1); int ans = 100000000; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(j == 1) dp[i][j] = dp[i - 1][j] + abs(a[i] - h[j]);//设dp[i][1]为最小的 else dp[i][j] = min(dp[i][j - 1],dp[i - 1][j] + abs(a[i] - h[j]));//这一步就是求出最小的dp[i][j] if(i == n) ans = min(dp[i][j],ans);//最后统计答案 } } printf("%d",ans); return 0; }