これは自力では解けなかったな。
https://codeforces.com/contest/1082/problem/F
問題
N種類の電話番号と、それぞれの入力回数が与えられる。
これらを入力するわけだが、ここでK個のショートカットキーを定義できる。
これらショートカットキーは、任意に決めることができ、番号のprefixの入力にのみ利用できる。
適切なショートカットキーを設定したとき、ショートカットキー以外のボタン押下回数を最小化せよ。
解法
Trie木を作り、そこでDPしていく。
各状態について、以下を求めていこう。
f(v, d, k) := Trie木のv以下のsubtreeにおいて、最寄りのショートカットキー設定済みの祖先の位置がdで、v以下でk回ショートカットキーを定義済み
あとは木DPの要領で、子頂点毎のショートカットキー設定回数が計K回となるように足し合わせていく。
int id=1; int nex[505][10]; int D[555]; int val[555]; int memo[555][555][12]; int N,K; string S[505]; int M[505]; int dfs(int cur,int pd,int K) { if(memo[cur][pd][K]>=0) return memo[cur][pd][K]; int dp[11]={}; int i,j,k; FOR(i,10) if(nex[cur][i]>=0) { int tmp[11]={},tmp2[11]={}; FOR(j,11) tmp[j]=dfs(nex[cur][i],pd,j); FOR(j,11) tmp2[j]=1<<30; FOR(j,11) FOR(k,11) if(j+k<=10) tmp2[j+k]=min(tmp2[j+k],dp[j]+tmp[k]); swap(dp,tmp2); } int ret=dp[K]+val[cur]*(D[cur]-pd); // take here if(K>0) ret=min(ret,dfs(cur,D[cur],K-1)); return memo[cur][pd][K]=ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; MINUS(nex); FOR(i,N) { cin>>S[i]>>M[i]; int cur=0; FORR(s,S[i]) { s-='0'; if(nex[cur][s]==-1) { nex[cur][s]=id++; D[nex[cur][s]]=D[cur]+1; } cur=nex[cur][s]; } val[cur]+=M[i]; } MINUS(memo); cout<<dfs(0,0,K)<<endl; }
まとめ
もっと計算量の多い方法は思いついたけど、これは思いつかなかった。