CF-1238E. Keyboard Purchase (狀壓dp)

題目鏈接

題意

長度$n$的字符串為排成一行,這個字符串由$m$個字符組成,你需要確定一種排列方式使得這個字符串的花費最少.

花費=$\sum _{i=1}^n|po{s}_{s_i}?po{s}_{s_{i?1}}|$

思路

狀壓$dp$

$dp[i]$ 表示i對應二進制的字符已經確定位置

如果字符x的位置已經確定,字符y的位置還未確定,$|po{s}_x?po{s}_y|$最小為1花費最少

$cnt$ 表示在狀態i下增加的最小花費

狀態轉移: $dp[i]=min(dp[i],dp[i?(1<<x)]+cnt)$

#include <bits/stdc++.h> const int maxn = 2e6 + 5; using namespace std; char s[maxn]; int dp[maxn], g[30][30]; int main() {int n, m;scanf("%d %d %s", &n, &m, s);for (int i = 1; i < n; ++i) {g[s[i]-'a'][s[i-1]-'a']++;g[s[i-1]-'a'][s[i]-'a']++;}dp[0] = 0;for (int i = 1; i < (1<<m); ++i) { // 枚舉確定的狀態int cnt = 0;dp[i] = 1e9;for (int j = 0; j < m; ++j) { // 確定的字符 和 未確定的字符 貢獻++for (int k = j+1; k < m; ++k) {if ((i>>j & 1) ^ (i>>k & 1)) {cnt += g[j][k];}}}for (int j = 0; j < m; ++j) {if (i >> j & 1) {dp[i] = min(dp[i], dp[i - (1<<j)] + cnt);}}}printf("%d\n", dp[(1<<m) - 1]);return 0; }

總結

以上是生活随笔為你收集整理的CF-1238E. Keyboard Purchase (状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。