苦戦したけど何とかクリア。
http://codeforces.com/contest/436/problem/C
問題
K個のレベルからなるステージがある。
各レベルはN*M文字の文字列で構成される。
このステージ表現を圧縮して送信する際、必要なバイト数を最小化せよ。
なお、レベルの送信順は入れ替えても良い。
各レベルの表現方法は以下のいずれかである。
- N*M文字すべてをそのまま送信する。N*Mバイト必要。
- 送信済みのいずれかのレベルの値および、そのレベルとの差分を送る。差分文字数×Wバイト必要。
解法
レベルxのあとyを送っても、yのあとxを送っても、かかるコストはN*M+diff(x,y)*Wで同じである。
よって送る順はどうでも良い。
後は差分を送る際適切なレベルを選択すればよい。
これには以下の処理を繰り返し行えばよい。
- 未送信のレベルのうち、バイト数最小のものを送る。
- 上記送信の結果、残された未送信の送信必要バイト数の最小値を更新する。
int N,M,K,W; string S[1001]; int cost[1001][1001]; int mcost[1001],tar[1001]; int vis[2001]; void solve() { int f,i,j,k,l,x,y; cin>>N>>M>>K>>W; FOR(i,K) { FOR(y,N) { string s; cin>>s; S[i]+=s; } } N=N*M; FOR(x,K) for(y=x+1;y<K;y++) { l=0; FOR(i,N) l+=S[x][i]!=S[y][i]; cost[x][y]=cost[y][x]=l*W; } FOR(x,K) mcost[x]=N; pair<int,int> R[2001]; x=0; ll ret=0; while(1) { int id=-1; FOR(i,K) if(vis[i]==0 && (id==-1 || mcost[i]<mcost[id])) id=i; if(id==-1) break; R[x].first=id+1; R[x].second=tar[id]; x++; ret+=mcost[id]; vis[id]=1; FOR(i,K) if(vis[i]==0 && mcost[i]>cost[id][i]) mcost[i]=cost[id][i],tar[i]=id+1; } _P("%lld\n",ret); FOR(i,K) _P("%d %d\n",R[i].first,R[i].second); }
まとめ
実は順番はどうでもいい、ということに気づくとあっさり。