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
",ans);
	return 0;
}