[Luogu P2893][USACO08FEB]修路Making the Grade

题意大致就是求把一段序列改成单调递增或者单调递减最小费用,费用是改前改后的高度之差的绝对值。那就直接用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;
}

 

上一篇:Luogu P2893 [USACO08FEB]修路Making the Grade


下一篇:[C\C++基础知识] main函数的参数argc和argv