BZOJ-1592: [Usaco2008 Feb]Making the Grade 路面修整

Description

给定一个序列，花一单位代价使得一个元素+1或-1。求使得原序列不降或者不升的最小花费。

考虑假设上升的话。如果相邻两个不合法，那么提高后一个肯定比降低前一个对于后效性更优。提到的标准只有前面最大的高度或者后面最小的高度。所以最后高度只能是原序列的集合。那么就可以用dp状态表示了。然后小优化一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[2100],b[2100],c[2100],tot,ans=1<<30;
int dp[2100][2100],dow[2100];
int Abs(int x){return x>0?x:-x;}
int main()
{
    scanf("%d",&n);
    int i,j;
    for(i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+n+1); c[1]=b[1]; tot=1;
    for(i=2;i<=n;i++) if(b[i]!=b[i-1]) c[++tot]=b[i];
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=tot;j++)
            dp[i][j]=dp[i-1][dow[j]]+Abs(c[j]-a[i]);
        dow[1]=1;
        for(j=2;j<=tot;j++)
            dow[j]=dp[i][j]<dp[i][dow[j-1]]-c[dow[j-1]]+c[j]?j:dow[j-1];
    }
    for(i=1;i<=tot;i++) ans=min(ans,dp[n][i]);
    for(i=1;i<n-i+1;i++) swap(a[i],a[n-i+1]);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=tot;j++)
            dp[i][j]=dp[i-1][dow[j]]+Abs(c[j]-a[i]);
        dow[1]=1;
        for(j=2;j<=tot;j++)
            dow[j]=dp[i][j]<dp[i][dow[j-1]]-c[dow[j-1]]+c[j]?j:dow[j-1];
    }
    for(i=1;i<=tot;i++) ans=min(ans,dp[n][i]);
    printf("%d",ans);
    return 0;
}