PKU 3638 Moogle
http://poj.org/problem?id=3638
h個のソート済みの整数が与えられる。
この中からc個の整数を選んで、選ばれなかった整数はその整数をはさむ一番近い選んだ整数で補完した値を設定する。
この時、正しい値とのズレの平均が最小になるような選び方をした時のズレの平均を求めろというような問題。
メモ化再帰しました。
最初選んだ範囲についていちいちズレを計算していてO(n^4)になっていてTLEしました。
予めある範囲のズレを計算しておくことでO(n^3)に落としてACもらえました。
bool vis[300][300]; double memo[300][300]; double x[300]; double error[300][300]; double rec(int re,int ed){ //cout<<re<<' '<<ed<<endl; if(re==0 && ed!=0)return 1LL<<50LL; if(re==0)return 0; if(vis[re][ed])return memo[re][ed]; vis[re][ed]=true; double& ret=memo[re][ed]=1LL<<50LL; for(int i=re-1;i<ed;++i) ret=min(ret, rec(re-1,i)+error[i][ed]); return ret; } void solve(){ int h,c; scanf("%d%d",&h,&c); rep(i,h){ scanf("%lf",x+i); rep(j,i){ error[j][i]=0; for(int k=j+1;k<i;++k) error[j][i]+=abs(x[j]+(x[i]-x[j])*(k-j)/(i-j)-x[k]); } } memset(vis,0,sizeof(vis)); printf("%.4f\n",rec(c-1,h-1)/h); } main(){ int t; scanf("%d",&t); while(t--) solve(); }