3638 Moogle

問題概要

数直線上にh個の家があり、それぞれの座標はx[i]である。
このうちc個の家の座標を記録し、残りの家の座標は線形補完により算出することにする。
このとき、それぞれの家の位置の誤差の平均の最小値を出力せよ。

h,c≦200を満たす。

解法

dp[i][j]に、i番目までの家のうち、i番目を記録させ、なおかつ記録した家の数がj個であるときの誤差の最小値をもつと、
dp[i][j]=min{dp[k][j-1]+err[k][i]}の漸化式が立つのでDPできる。

err[k][i]は事前に計算しておき、計算量を節約する。

ソースコード

double dp[201][201],err[201][201];

int main(){
	int t,h,c,x[200];
	scanf("%d",&t);
	rep(T,t){
		scanf("%d%d",&h,&c);
		rep(i,h)scanf("%d",x+i);
		
		rep(i,h)rep(j,h)dp[i][j]=INF;
		rep(j,h)rep(i,j)
		{
			err[i][j]=0;
			for(int k=i+1;k<j;k++)err[i][j]+=
			abs(x[i]+(x[j]-x[i])*1.0*(k-i)/(j-i)-x[k]);
		}
		dp[0][1]=0;
		for(int i=1;i<h;i++)for(int j=2;j<=i+1;j++)rep(k,i)
		{
			dp[i][j]=min(dp[i][j],dp[k][j-1]+err[k][i]);
		}
		printf("%.4f\n",dp[h-1][c]/h);
	}
	return 0;
}