CF1082F - Speed Dial

Posted on Edited on In

CF1082F - Speed Dial

题目大意

给定 \(n\) 个电话号码，你可以随意生成 \(k\) 个快捷键，每个快捷键是一个数字串

最终拨号方式：

选择 至多一个 快捷键按下，对于剩余部分手动补全，且不允许退格

每个电话号码有拨打次数，最小化手动补全部分的长度总和


分析

如果每次选定一个集合使其公用一个快捷键，那么其长度必然是集合中所有串的 \(\text{LCP}\)

假设确定了一个 \(\text{LCP}\) ，那么对应的串集合容易发现就是 \(\text{trie}\) 树上的一个子树

于是先将所有串加入 \(\text{trie}\) 树，此时问题转化为

选择至多 \(k\) 个 \(\text{LCP}\) （默认根节点选了且没有代价），使得每个电话号码到其祖先中最深 \(\text{LCP}\) 的距离之和最小

由于有拨打次数的限制，且其数值相对较大，难以存入dp状态

于是想到在祖先钦定 \(\text{LCP}\) ，然后从子树取值

令 \(dp_{u,i,j}\) 表示计算 \(u\) 子树内的答案，已经钦定祖先中最深的 \(\text{LCP}\) 长度为 \(i\) ，且在子树内又钦定了 \(j\) 个 \(\text{LCP}\)

合并子树时对于每个 \(i\) ，背包合并 \(j\) ，决策 \(u\) 自己是否选为 \(\text{LCP}\) 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

const int N=510,INF=1e9+10;

int n,m;
int trie[N][10],cnt,c[N];
char s[N];
int dp[N][N][12];
int F[N][12],G[12],dep[N];

void dfs(int u) {
	for(int v:trie[u]) if(v) dep[v]=dep[u]+1,dfs(v);
	memset(F,63,sizeof F);
	rep(i,0,dep[u]) F[i][0]=c[u]*(dep[u]-i);
	for(int v:trie[u]) if(v) {
		rep(j,0,dep[u]) {
			rep(k,0,m) G[k]=F[j][k],F[j][k]=INF;
			rep(k,0,m) rep(d,0,m-k) cmin(F[j][k+d],G[k]+dp[v][j][d]);
		}
	}
	rep(d,0,dep[u]) {
		rep(i,0,m) dp[u][d][i]=INF;
		rep(i,0,m) {
			cmin(dp[u][d][i+1],F[dep[u]][i]);
			cmin(dp[u][d][i],F[d][i]);
		}
	}
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) {
		scanf("%s",s+1);
		int u=0;
		for(int j=1;s[j];++j) {
			int &v=trie[u][s[j]-'0'];
			if(!v) v=++cnt;
			u=v;
		}
		c[u]+=rd();
	}
	dfs(0);
	int ans=INF;
	rep(i,0,m) cmin(ans,dp[0][0][i]);
	printf("%d\n",ans);
}