题解 P2893 【[USACO08FEB]修路Making the Grade】

· · 题解

欢迎来看看呀

题目链接

这道题代码虽然简单，但是状态转移方程还是比较难想的

首先我们可以贪心地发现一个性质，要使修理完的路花费最小，每条路必然都会是原来已经存在的高度，不然就会造成损失

接下来该怎么处理呢？考虑利用上面的性质来设计一个状态

先将输入的数据离散化一下，b[i]表示第i高的路的高度，可以用f[i][j]表示当第i条路的高度为b[j]时，修理完前i条路所用的最小花费，转移不是很难想

f[i][j]=min(f[i-1][k])+|a[i]-b[j]|(k\in[1,j))

其中min(f[i-1][k])可以用一个数组记录下来，就可以把O(n^3)的复杂度优化到O(n^2)

接下来是代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[2003],b[2003],mi[2003][2003],f[2003][2003];//mi数组用来记录min(f[i-1][k])
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);//离散化
    for(int i=1;i<=n;i++)
        mi[i][0]=1e9;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            f[i][j]=mi[i-1][j]+abs(a[i]-b[j]),mi[i][j]=min(mi[i][j-1],f[i][j]);     
    }
    cout<<mi[n][n];
    return 0;
}