これは自力では解けず。
http://community.topcoder.com/stat?c=problem_statement&pm=13857
問題
N頂点からなる木Tを作りたい。
木のコストS(T)は、全頂点ペア間の距離の和だとする。
S(T) mod M == Rとなる最小のS(T)が存在するならそれを答えよ。
解法
p頂点の木T1とq頂点の木T2の間を辺でつないだ木T3を考える。
S(T)にはその辺によりp*q分コストが加算されることになる。
すなわちS(T3)=S(T1)+S(T2)+p*qとなる。
この考えをもとに、n頂点でMで割った余りがrになる木の最小コストをdp[n][r]=最小コストの形で管理し、DPで更新して最後にdp[N][R]を答えればよい。
1点注意点として、上記式では2つの木の連結による辺のコストをp*qで計算している。
しかし実際は最終的には辺の両端は計N頂点になることになることを考慮しなければならない。
よってT1側の木はそれ以上他の木を連結せずT2側にのみ連結する、と仮定し、S(T3)=S(T1)+S(T2)+p*(N-p)で更新していけば問題ない。
int dp[51][101]; class ExactTree { public: int getTree(int n, int m, int r) { MINUS(dp); dp[1][0]=0; int i,j,x,y; for(i=2;i<=n;i++) { for(j=1;j<i;j++) { FOR(x,m) FOR(y,m) if(dp[j][x]>=0 && dp[i-j][y]>=0) { int z=dp[j][x]+dp[i-j][y]+j*(n-j); if(dp[i][z%m]==-1) dp[i][z%m]=z; dp[i][z%m]=min(dp[i][z%m],z); } } } return dp[n][r]; } }
まとめ
距離の総和を求める場合には、各辺を何回またぐかを考えればよい。
しばしば使うテクなのに忘れてたな…。