题目链接:点我啊╭(╯^╰)╮
题目大意:
长度为 n ≤ 1 e 5 n≤1e5n≤1e5 的串,字符集为 m ≤ 20 m≤20m≤20
键盘上有对应的 m mm 个键,排成一排
键位自定义,问输出这个串的最短总和距离为多少??
解题思路:
m mm 只有 20 2020, 考虑状压
设 c n t [ x ] [ y ] cnt[x][y]cnt[x][y] 为字母 x xx 到 y yy的总次数
d p [ s ] dp[s]dp[s] 为状态为 s ss 时,已经将 s ss 每个状态位的字符放到键盘上,移动的最少距离
接下来考虑距离的影响
考虑每次转移时,新的字母 x xx 放到键盘的最右边,设 p o s [ x ] pos[x]pos[x] 为 x xx 在键盘上的位置
则从 d p [ s ] − > d p [ s ∣ 1 < < x ] dp[s] -> dp[s | 1<<x]dp[s]−>dp[s∣1<<x],要考虑 x xx 到 s ss 里的字母里的距离 与 x xx 到 s ss 外的字母里的距离
∑ k ∈ S c n t [ x ] [ k ] × ( p o s [ x ] − p o s [ k ] ) + ∑ k ∉ S c n t [ x ] [ k ] × ( p o s [ k ] − p o s [ x ] ) \sum_{k\in S}{cnt[x][k] \times (pos[x] - pos[k])} + \sum_{k\notin S}{cnt[x][k] \times (pos[k] - pos[x])}∑k∈Scnt[x][k]×(pos[x]−pos[k])+∑k∈/Scnt[x][k]×(pos[k]−pos[x])
每次转移需要计算 S SS 状态下,上式的值,发现可以预处理
预处理的是每个 S SS 的每个状态位与每个非状态位的距离总和 d [ S ] d[S]d[S]
那么转移的时候从d p [ s ] − > d p [ s ∣ 1 < < x ] , d p [ s ∣ 1 < < x ] = m i n ( . . . , d p [ s ] + d [ s ] ) dp[s] -> dp[s | 1<<x],dp[s | 1<<x] = min(...,dp[s] + d[s])dp[s]−>dp[s∣1<<x],dp[s∣1<<x]=min(...,dp[s]+d[s])
这样通过每次转移,都处理了键盘里的字母与非键盘里的字母的距离
时间复杂度:O ( m 2 × 2 m + m × 2 m ) O(m^2 \times 2^m + m \times 2^m)O(m2×2m+m×2m)
达到了 4 e 8 4e84e8,很明显 c f cfcf 是可以卡过的,但考虑更优的做法的话
对于 ∑ k ∈ S c n t [ x ] [ k ] × ( p o s [ x ] − p o s [ k ] ) + ∑ k ∉ S c n t [ x ] [ k ] × ( p o s [ k ] − p o s [ x ] ) \sum_{k\in S}{cnt[x][k] \times (pos[x] - pos[k])} + \sum_{k\notin S}{cnt[x][k] \times (pos[k] - pos[x])}∑k∈Scnt[x][k]×(pos[x]−pos[k])+∑k∈/Scnt[x][k]×(pos[k]−pos[x])
因为 p o s [ x ] = = S pos[x] == Spos[x]==S 里的 1 11 的个数,但 p o s [ k ] pos[k]pos[k] 未知,如果考虑 p o s [ k ] pos[k]pos[k] 则会到达 m 2 × 2 m m^2 \times 2^mm2×2m
这里我们只考虑插入字母 x xx 时,p o s [ x ] pos[x]pos[x] 对转移的影响
则上式变为:∑ k ∈ S c n t [ x ] [ k ] × p o s [ x ] − ∑ k ∉ S c n t [ x ] [ k ] × p o s [ x ] \sum_{k\in S}{cnt[x][k] \times pos[x]} - \sum_{k\notin S}{cnt[x][k] \times pos[x]}∑k∈Scnt[x][k]×pos[x]−∑k∈/Scnt[x][k]×pos[x]
这样我们在预处理时,设 d [ s ] [ x ] d[s][x]d[s][x] 为 x ∉ s , ∑ k ∈ s c n t [ x ] [ k ] x \notin s,\sum_{k \in s}{cnt[x][k]}x∈/s,∑k∈scnt[x][k]
发现 d [ s ] [ x ] d[s][x]d[s][x] 也可以通过子集的状态转移,设 i ∈ s i \in si∈s
d [ s ] [ x ] = d [ s d[s][x] = d[sd[s][x]=d[s ^ i ] [ x ] + c n t [ x ] [ i ] i][x] + cnt[x][i]i][x]+cnt[x][i]
只需要知道一个 i ∈ s i \in si∈s,考虑树状数组里的 s & − s s \& {-s}s&−s 则可以得到 s ss 里的最低位的 1 11
预处理之后,d p dpdp 的转移则要考虑位置的影响
d p [ n s ] = m i n ( d p [ n s ] , d p [ s ] + p o s [ x ] ∗ ( d [ s ] [ x ] − d [ ( ( 1 < < m ) − 1 ) dp[ns] = min(dp[ns], dp[s] + pos[x] * (d[s][x] - d[((1<<m)-1)dp[ns]=min(dp[ns],dp[s]+pos[x]∗(d[s][x]−d[((1<<m)−1) ^ n s ] [ x ] ) ) ns][x]))ns][x]))
那么问题来了,为什么只考虑 p o s [ x ] pos[x]pos[x] 对转移的影响,而不考虑 p o s [ k ] pos[k]pos[k] 的影响?
观察 ∑ k ∈ S c n t [ x ] [ k ] × ( p o s [ x ] − p o s [ k ] ) − ∑ k ∉ S c n t [ x ] [ k ] × ( p o s [ k ] − p o s [ x ] ) \sum_{k\in S}{cnt[x][k] \times (pos[x] - pos[k])} - \sum_{k\notin S}{cnt[x][k] \times (pos[k] - pos[x])}∑k∈Scnt[x][k]×(pos[x]−pos[k])−∑k∈/Scnt[x][k]×(pos[k]−pos[x])
发现对于 p o s [ k ] pos[k]pos[k],在不断的转移计算过程中,最终会全部抵消掉,总和为 0 00
也就是 p o s [ k ] pos[k]pos[k] 对最终答案是没用影响的
那么现在的状压 d p dpdp 所表示的就不是原本的状压了,中间的过程状态都是错的
但最终的结果是正确的的(QwQ ~~~)
时间复杂度:O ( m × 2 m ) O( m \times 2^m)O(m×2m)
核心:预处理状态转移,子集优化dp
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m, cnt[25][25];
int d[1<<21][25], dp[1<<21];
char s[maxn];
int main() {
scanf("%d%d%s", &n, &m, s+1);
for(int i=1; i<n; i++){
cnt[s[i]-'a'][s[i+1]-'a']++;
cnt[s[i+1]-'a'][s[i]-'a']++;
}
for(int s=1; s<1<<m; s++)
for(int i=0; i<m; i++)
d[s][i] = d[s & (s - 1)][i] + cnt[i][__builtin_ffs(s) - 1];
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int s=0; s<1<<m; s++){
for(int i=0; i<m; i++){
if(1 << i & s) continue;
int ns = 1 << i | s;
int pos = __builtin_popcount(s);
dp[ns] = min(dp[ns], dp[s] + pos * (d[s][i] - d[((1<<m)-1) ^ ns][i]));
}
}
printf("%d\n", dp[(1<<m)-1]);
}