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

· · 题解

在满足答案最小化的前提下，一定存在一种构造新序列的方案，使得新序列中的值全都在原序列中出现过。

证明略。

以上摘自《算阶》。

为了方便起见，只考虑不下降的情况

设f[ i,j ]为修改到第i段路，且修改后高度为 j 的最优值

根据引理得，j 一定在原序列中出现过，所以可将 j 离散化

f[ i,j ]的意义变为修改到第 i 段路，且修改后高度为第 j 段路高度的最优值

由此可得:

f[ i,j ]=min(f[ i-1,k ]+\mida[ i ]-a[ j ]\mid)，k\in[ 1,n ]\bigcapa[ k ]<=a[ j ]，a代表原序列值

CODE

for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            if(a[k]<=a[j])
                f[i][j]=min(f[i][j],f[i-1][k]+abs(a[i]-a[j]));

时间复杂度O(N^3)，无法承受

声明：本人语文很糟，下述优化讲得不是很好。如果想清楚了解，可以私信。

根据DP方程的定义，很容易看出，i 和 j 的循环是不可省的。

所以优化从 k 入手。

观察这句话。

for(int k=1;k<=n;++k)
    if(a[k]<=a[j])
        f[i][j]=min(f[i][j],f[i-1][k]+abs(a[i]-a[j]));

我们很容易看出，在找满足 a[ k ]<a[ j ] 的 k，检查能否更新时花费了大量时间。

这启发我们在O(1)的时间内实现转移。

可以这样做：新建一个结构体 b，存 a 的值和对应的下标，以值为关键字从小到大排序。

排完序后，用一个数组 tong，执行以下操作：

for(int i=1;i<=n;++i)
    tong[b[i].id]=i;

这样，tong[ j ] 就代表原始序列中的第 j 个元素在排序后序列元素的下标。

新建一个q数组，设 q[ j ] 代表排序后序列中，第 j 小DP值。

这样，就可以用 q[ tong[ j ] ] 以O(1)复杂度访问到 f[ i-1,k ] 中满足条件的最小值

每轮转移结束后，更新 q[ ] 中的DP值

问题又来了。该如何更新呢？

回顾定义，f[ i,j ] 中 j 的定义为修改后高度为第j段路高度的最优值，而 q[ j ] 的定义为排序后序列中，第 j 小DP值。

也就是说，q[ tong[ j ] ]=f[ i,j ]（i是一轮DP结束后未自加的i）。

因为要求的序列满足单调不下降，所以比这次修改后土坡高的上一修改后土坡都能参与转移，我们只需保留DP值最小的。

换言之，q[ ]是单调递减的，可以在 q[ tong[ j ] ]=f[ i,j ] 赋值完后，再遍历一次更新最值。

int tmp=2139062143;//tmp初始为一个极大值
    for(int j=1;j<=n;++j)
        if(q[j]>=tmp)
            q[j]=tmp;
        else tmp=q[j];

最开始q[ ]初值均赋0，因为没有进行DP。

时间复杂度O(N^2)，可以接受 （虽然常数很大）

CODE

#include<bits/stdc++.h>
using namespace std;
const int INF=2139062143;
const int N=3000;
struct kkk{
    int id,x;
}b[N];
int f[N][N],a[N];
int tong[N],q[N];
int n,ans=INF;
bool cmp(kkk x,kkk y){
    return x.x==y.x?x.id<y.id:x.x<y.x;
}
bool cop(kkk x,kkk y){
    return x.x==y.x?x.id<y.id:x.x>y.x;
}
int main(){
    scanf("%d",&n);
    memset(f,127,sizeof(f));
    for(int i=0;i<=n;++i)
        f[0][i]=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i].id=i;b[i].x=a[i];
    }
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;++i)
        tong[b[i].id]=i;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            f[i][j]=min(f[i][j],q[tong[j]]+abs(a[i]-a[j]));
        for(int j=1;j<=n;++j)
            q[tong[j]]=f[i][j];
        int tmp=2139062143;
        for(int j=1;j<=n;++j)
            if(q[j]>=tmp)
                q[j]=tmp;
            else tmp=q[j];
    }
    for(int i=1;i<=n;++i)
        ans=min(f[n][i],ans);
    memset(q,0,sizeof(q));
    memset(f,127,sizeof(f));
    for(int i=0;i<=n;++i)
        f[0][i]=0;
    sort(b+1,b+1+n,cop);
    for(int i=1;i<=n;++i)
        tong[b[i].id]=i;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            f[i][j]=min(f[i][j],q[tong[j]]+abs(a[i]-a[j]));
        for(int j=1;j<=n;++j)
            q[tong[j]]=f[i][j];
        int tmp=2139062143;
        for(int j=1;j<=n;++j)
            if(q[j]>=tmp)
                q[j]=tmp;
            else tmp=q[j];
    }
    for(int i=1;i<=n;++i)
        ans=min(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

最后，附上某位大佬的O(NlogN)贪心26行代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[2001],f[2001][2001];
int ans1,ans2; 
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int,vector<int>,less<int> >w;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){ 
        scanf("%d",&a[i]);
        q.push(a[i]);
        if(a[i]>q.top()){
            ans1+=a[i]-q.top();
            q.pop(); q.push(a[i]);
        }
    }
    for(int i=1;i<=n;i++){
        w.push(a[i]);
        if(a[i]<w.top()){
            ans2+=w.top()-a[i];
            w.pop(); w.push(a[i]);
        }
    }
    printf("%d",min(ans1,ans2));
    return 0;
}

所以用DP做的都是猪脑子。