题解 P2893 【[USACO08FEB]Making the Grade G】

· · 题解

其实这边题解的思路和楼上基本差不多

但是看到还可以提交

那怎么能不交呢

并且hack掉了楼上某一篇题解中的hack

希望能为大家带来一些新的思考

首先这道题数据比较水，只需要考虑单调不降的情况即可但事实上单调不增和单调不降其实是一样的，只需要改变一下递推顺序即可。

首先考虑贪心，我们考虑把每一个路的海拔提升至上一个路海拔。例如

9
5 5 5 1 1 1 5 5 5

则只需要将中间的三个1升高到5，总花费为12

但是，这种做法是非常好卡掉的，看下面这组数据

5
1000000000 0 0 0 1000000000

如果按照上面的贪心思想答案应为3000000000（不用数了有9个铃）。很显然，这是错误的，我们只需要将第一个路由10^9降为0即满足题意，总花费为10^9。

贪心解决不了的问题，一般是动态规划。——rxz

那么我们来考虑动态规划，容易想到状态f[i][j]表示

我们看到j的范围高达10^9,而总共只有不多余2000个数，所以考虑离散化，把路高从小到大排序，存在b[]中。修改一下状态。 f[i][j] 表示处理到第i个路，第i个路高为b[j]时的最小花费。

接下来考虑转移，很显然的是

f[i][j] = min([i-1][k]) + abs(a[i]-b[j]),0<k<j+1

这样复杂度为O(n^3)，不能接受。下面考虑优化。

我们发现，每一次我们都花费了O(n) 来寻找min([i-1][k])，那么我们能否在处理第i-1个路的时候就顺便将其算出来呢？显然是可以的。具体参见代码

则答案应为 min(f[n][k])

最后注意边界条件与数组初始化就可以了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int n;
int a[maxn],b[maxn];
int f[maxn][maxn],mn[maxn][maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    memset(mn,0x7f,sizeof(mn));
    memset(mn[0],0,sizeof(mn[0]));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            f[i][j] = mn[i-1][j] + abs(a[i]-b[j]);
            mn[i][j] = min(mn[i][j-1],f[i][j]);
        }
    }
    for(int i=2;i<=n;++i) f[n][i]=min(f[n][i],f[n][i-1]);
    printf("%d",f[n][n]);
    return 0;
}