[bzoj1592][Usaco09Feb]Making the Grade 路面修整

Making the Grade 路面修整 bzoj-1592

题目大意：给你n段路，每段路有一个高度h[i]，将h[i]修改成h[i]$\pm\delta$的代价为$\delta$，求将这n段路修成非严格单调的最小代价。

注释：1$\le$n$\le$2000，$1\le A_i\le 10^9$。

想法：我们先考虑单调递增。显然，我们期望所有数都尽量靠近原来的数。a数组是原来的高度数组，b数组是按照a的排序数组

　　状态：dp[i][j]表示前i段路，且第j段路变成了b[j]的方案数。

　　转移：f[i][j]=min(f[i-1][k])+abs(a[i]-b[j])(1<=k<=j)。

　　具体地，这个$n^3$的dp的min我们可以在转移的过程中直接处理出，所以是$n^2$的。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

int n,m,mindp[2009][2009],dp[2009][2009],a[2009],b[2009],t[2009],ans;

void original()

{

  for (int i=0;i<=n;i++)

  for (int j=0;j<=m;j++)

  mindp[i][j]=dp[i][j]=0;

}

void dispose()

{

    for (int i=1;i<=n;i++)

        for (int j=1;j<=m;j++)

  		{

            dp[i][j]=mindp[i-1][j]+abs(a[i]-b[j]);

            if (j!=1) mindp[i][j]=min(mindp[i][j-1],dp[i][j]);

            else mindp[i][j]=dp[i][j];

  		}

}

int main()

{

 	scanf("%d",&n);

 	for (int i=1;i<=n;i++)

  	{

        scanf("%d",&a[i]);

        t[i]=a[i];

    }

    sort(t+1,t+1+n);

    int now=-1;

    for(int i=1;i<=n;i++)

        if(now!=t[i]) b[++m]=t[i],now=t[i];

    original();

    dispose();

    ans=mindp[n][m];

    for(int i=1;i<=m/2;i++) swap(b[i],b[m-i+1]);

    original();

    dispose();

    ans=min(ans,mindp[n][m]);

    printf("%d\n",ans);

    return 0;

}

小结：dp总是神奇的qwq

巴特西

[bzoj1592][Usaco09Feb]Making the Grade 路面修整_动态规划

最新文章

热门文章