この考え方は面白かった。
http://codeforces.com/contest/321/problem/E
問題
N人の人が一列に並んでいるので、この列をK個のグループに分割したい。
分割後の各グループは1人以上いなければならない。
この時、i番とj番の人が同じグループにいたら、Q[i][j]のスコアがもらえる。
総スコアを最大化せよ。
解法
まずa番~b番の連続する人が同じグループにいる場合、その総スコアsum(a,b)をO(1)で出せるように累積和を取っておく。
シンプルな回答としては、[今見ている人の番号][残りグループ数]で状態を持ち、最大スコアを更新すればよい。
dp[id][groups] = max(dp[k][groups-1]+sum(k+1,id) )のような感じ。
ただしこれだとO(N^2*K)かかりTLEする。
この計算量を何とかしなければならない。
ここからEditorialを見て回答。
dp[id][groups] = max(dp[k][groups-1]+sum(k+1,id) )
について、最大値となるkをopt[id][groups]とする。
すなわちdp[id][groups] = dp[opt[id][groups]][groups-1]+sum(opt[id][groups]+1,id)。
このopt[id][groups]はidに対し昇順で、
opt[0][groups] ≦ opt[1][groups] ≦ opt[2][groups] ....
となる。
よってdp[id][groups-1]が一通り定まっているとき、二分探索を使いopt[id][groups]を求める。
元のO(N^2*K)の式では、0 ≦ opt[id][groups] < idとなるので時間がかかっていた。
しかしまずopt[N/2][groups]を求めておけば、id>N/2においてopt[N/2][groups] ≦ opt[id][groups] < idとなるので検索範囲が縮まる。
あとは同様に範囲を半々にしていく。
これにより全体でO(N*K*logN)程度の計算量に落とすことができる。
int N,K; int U[5002][5002]; int S[5002][5002]; ll dp[5002][5002]; int costs(int l,int r) { return (S[r+1][r+1]-S[l][r+1]*2+S[l][l])/2; } void dodo(int step,int L,int R,int OL,int OR) { if(L>R) return; int M=(L+R)/2; int i,op; for(i=OL;i<=OR;i++) { if(dp[step][M+1]>dp[step-1][i]+costs(i,M)) { dp[step][M+1] = dp[step-1][i]+costs(i,M); op=i; } } dodo(step,L,M-1,OL,op); dodo(step,M+1,R,op,OR); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(y,N) FOR(x,N) cin>>U[y][x]; FOR(y,N) { FOR(x,N) S[y+1][x+1]=S[y+1][x]+U[y][x]; FOR(x,N) S[y+1][x+1]+=S[y][x+1]; } FOR(y,N+1) FOR(x,N+1) dp[y][x]=1LL<<40; dp[0][0]=0; FOR(k,K) dodo(k+1,0,N,0,N); cout << dp[K][N] << endl; }
まとめ
optが昇順になることは推測ついても、その後こういう二分探索を行うことは思いつかなかった。
このテクは覚えておこう。