bzoj 1592 dp

就是dp啊

f[i][j]表示到第i位，最后一位高度是j的最小花费

转移：：f[i][j]=minn(f[i-1][k])+abs(a[i]-num[j]);(k<=j)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int f[2005][2005],n,a[2005],b[2005],num[2005];
int ans;
bool bo;
int main()
{
    scanf("%d",&n);
    memset(f,0x7f,sizeof f); ans=0x7fffffff;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        num[i]=a[i];
        b[n-i+1]=a[i];
    }
    num[0]=0;
    sort(num,num+n+1);
    int num_cnt=unique(num,num+n+1)-num;
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        int minn=0x3f3f3f3f;
        for(int j=0;j<num_cnt;j++){
            minn=min(minn,f[i-1][j]);
            f[i][j]=minn+abs(a[i]-num[j]);
        }
    }
    for(int j=0;j<num_cnt;j++)
        ans=min(ans,f[n][j]);
    memset(f,0x7f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        int minn=0x3f3f3f3f;
        for(int j=0;j<num_cnt;j++){
            minn=min(minn,f[i-1][j]);
            f[i][j]=minn+abs(b[i]-num[j]);
        }
    }
    for(int j=0;j<num_cnt;j++)
        ans=min(ans,f[n][j]);
    printf("%d
",ans);
    return 0;
}