Codeforces Edu 74 E. Keyboard Purchase 【状压DP +贡献】

本文主要是介绍Codeforces Edu 74 E. Keyboard Purchase 【状压DP +贡献】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

E. Keyboard Purchase

题意

给定一个长度为 $n$ 的字符串 $s$ 仅由前 $m$ 个小写字母组成

现在要求求出包含前 $m$ 个小写字母的键盘，使得在键盘上敲出 $s$ 要移动的距离最短

移动总距离为：${\sum }_{i=2}^n|po{s}_{s_{i-1}}-po{s}_{s_i}|$

$po{s}_{s_i}$ 是 $s_i$ 在键盘上的位置

思路

由于 $m$ 很小，我们考虑在键盘上跑状压 $DP$，如果当前已经排好了集合 $S$ 中的那些位，枚举当前的字母的话，假设当前枚举的不在 $S$ 中的字母为 $i$，那么我们就需要找到 $s$ 中和字母 $i$ 相邻的那些字母 $j$，因为它们相邻，所以要 $j\to i$ 或 $i\to j$ 移动，这个移动是在键盘上移动的。我们不妨以 $cnt[i][j]$ 来表示原 $s$ 中相邻的 $i-j$ 配对数量

那么这一位放 $i$ 的贡献为：

• ${\sum }_{j\in S}cnt[j][i]\times (po{s}_i-po{s}_j)$
• ${\sum }_{j\notin S}cnt[j][i]\times (po{s}_j-po{s}_i)$

对于 $j$ 是否已经在 $S$ 中分开考虑，已经在 $S$ 中的 $j$，后放置的 $i$ 的 $po{s}_i$ 一定大于 $po{s}_j$，反之也很容易得出相应结论。

那么我们把贡献中包含小标 $i$ 的提取出来，就变成了只和 $i$ 相关的贡献：

• ${\sum }_{j\in S}cnt[j][i]\times po{s}_i$
• ${\sum }_{j\notin S}cnt[j][i]\times (-po{s}_i)$

这就是 $i$ 的贡献了，可以发现：把所有字母的贡献加起来，一定是这个放置顺序的答案

我们只需要从贡献这个角度切入就可以很容易得出状压 $DP$ 的转移

时间复杂度：$O(m^2\cdot 2^m)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;const int M = 21;int cnt[M][M];
int dp[1 << M];int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n, m;std::cin >> n >> m;std::string s;std::cin >> s;fore(i, 1, n){++cnt[s[i] - 'a'][s[i - 1] - 'a'];++cnt[s[i - 1] - 'a'][s[i] - 'a'];}memset(dp, INF, sizeof(dp));dp[0] = 0;fore(S, 0, 1 << m)fore(i, 0, m)if(!(S >> i & 1)){int nS = S | 1 << i;int res = 0;int pos = __builtin_popcount(S);fore(j, 0, m){if(i == j) continue;if(S >> j & 1) res += cnt[i][j] * pos;else res -= cnt[i][j] * pos;}dp[nS] = std::min(dp[nS], dp[S] + res);}std::cout << dp[(1 << m) - 1];return 0;
}

这篇关于Codeforces Edu 74 E. Keyboard Purchase 【状压DP +贡献】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---