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

· · 题解

Link

P2893 [USACO08FEB]Making the Grade G

Solve

这道题实际上是有O(nlogn)的做法的，但是DP的做法还是能带来很多思考的

因为数据很大，所以我们不能直接拿数值DP考虑用下标DP

这里我们有一个结论：

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

证明：

数学归纳法。命题N=1显然成立

设结论对N=k-1成立，此时构造出的序列为B_1~B_{k-1}

当N=k时，若B_{k-1}≤A_k，则令B_k=A_k满足单调性且命题成立。

否则，要么令B_k=B_{k-1}，命题仍成立，要么存在一个j,令B_j，B_{j+1},...,B_k为同一个值v，设A_j,A_{j+1},...,A_k的中位数是mid，若mid≥B_{j-1}则有v=mid，否则有v=B_{j-1}。无论哪种情况，B_1~B_k中的数都在A中出现过。

证毕.

有了这个结论，就很简单了

我们定义F[i][j]表示前i个数，第i个数是b[j]的最优解，(b是排序后的a，懒得离散了)

显然转移方程就比较简单了

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

但是这个转移方程直接推是O(n^3)的，不够优秀

我们发现min(F[i][k]每次都去找k<j的最小值，所以可以用一个数组Min[i][j]提前记一下F[i][1-j]的最小值,每次转移的时候把Min[i-1][j]当做min(F[i][j])就好了，最后更新Min[i][j]

这种维护前面某个状态的最小值来降低维度的方法是可以转移的，如果前面某个量是线性增长的，就可以用记一下前面的最优答案方便转移。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int N,ans=1<<30,a[maxn],b[maxn],F[maxn][maxn],Min[maxn][maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    freopen("P2893.in","r",stdin);
    freopen("P2893.out","w",stdout);
    N=read();
    for(int i=1;i<=N;i++)a[i]=read(),b[i]=a[i];
    sort(b+1,b+1+N);
    memset(Min,63,sizeof Min);
    memset(Min[0],0,sizeof Min[0]);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            F[i][j]=Min[i-1][j]+abs(a[i]-b[j]);
            Min[i][j]=min(F[i][j],Min[i][j-1]);
        }
    for(int i=1;i<=N;i++)ans=min(ans,F[N][i]);

    for(int i=1;i<=N/2;i++)swap(b[i],b[N-i+1]);
    memset(F,0,sizeof F);
    memset(Min,63,sizeof Min);
    memset(Min[0],0,sizeof Min[0]);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            F[i][j]=Min[i-1][j]+abs(a[i]-b[j]);
            Min[i][j]=min(F[i][j],Min[i][j-1]);
        }
    for(int i=1;i<=N;i++)ans=min(ans,F[N][i]);
    printf("%d\n",ans);
    return 0;
}