[リニアDP]路面整備

FJは農場の中にあるでこぼこした土道をよく修理するつもりだ.乳牛たちの要求によると、修理後の路面の高さは単調に上昇または単調に低下しなければならない.つまり、高さの上昇と高さの低下の区間は修理の道に同時に現れない.
全経路がNセグメントに分割され、N個の整数A 1,...,AN(1<=N<=2000)は、各経路の高さ(0<=Ai<=1億円)を順次記述している.FJは、修繕された道路の各区間の高さとして、N個の要素を適切に含む上昇または下降しないシーケンスB 1,...,BNを見つけることを望んでいる.各区間の敷物が高いか低いかの費用が同じであるため、道路修理の総支出は|A 1−B 1|+|A 2−B 2|+...+|AN−BN|と表すことができ、FJのこの工事における最小支出はいくらであるか計算してください.FJはこの支出がmaxintを超えないことを保証します.
1行目を入力:1個の整数を入力:N
第2…N+1行:第i+1行1個整数:A_i
出力1行目:1つの正の整数を出力し、FJが道路を高さが上昇しない、または高さが低下しない最小費用サンプル入力[コピー]7 1 3 3 2 4 5 3 9サンプル出力3ヒント出力説明を示す:
FJは、第1の高さが3の区間の高さを2に減らし、第2の高さが3の区間の高さを5に増やし、総費用は|2−3|+|5−3|=3であり、各区間の高さは1つの下がらないシーケンス1,2,4,5,5,9である.
ラベルusaco 2008 feb-gold
分析:基礎の線形dp、まず1つの合法的な方案はきっと構築したシーケンスBを満たすことができて、∀x∈B∀x∈B∀x∈Bにx∈A x∈Aがあって、したがってBシーケンスは必ず複数のx(x∈A)の連続セグメントから構成されるので、まずAを離散化して消費を低減し、f[i][j]f[i][j]f[i][j]f[i][j]f[i][j]f[i][j]を完了前のi個数とし、最後の数がjの最小費用とすると、f[i][j]=m i n(f[i][i−1][k]+∣A[i]−j∣)f[i][j]=min(f[i−1][k]+|A[i]−j|)f[i][j]=min(f[i]=min(f[i−1][k]+k]=min(f[i−1[k]+k∣A[i]−j∣,O(n 2)O(n^2)O(n 2)DP
コード:

#include
using namespace std;
const int SIZE=2010;
int a[SIZE],c[SIZE],nums[SIZE];
int f[SIZE][SIZE];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		nums[i]=a[i];
	}
	sort(nums+1,nums+n+1);
	int m=unique(nums+1,nums+n+1)-nums-1;
	for(int i=1;i<=n;i++)
		c[i]=lower_bound(nums+1,nums+m+1,a[i])-nums;
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		int temp=f[i-1][0];
		for (int j=1;j<=m;j++){
			temp=min(temp,f[i-1][j]);
			f[i][j]=temp+abs(a[i]-nums[j]);
		}
	}
	int ans=1<<30;
	for(int i=1;i<=m;i++)
		ans=min(ans,f[n][i]);
	cout<<ans<<endl;
}