こういうのを素早く処理できるようになりたい
問題概要
長さ の 種類の文字からなる文字列 が与えられる。いま、 種類の文字の順列 として考えられる 通りの並びのうち最適なものを求めたい。
順列のスコアは、 上のすべての連続する 2 文字について、それらの文字の における index の差分を合計した値で決まる。
このスコアの最小値を求めよ。
制約
考えたこと
実質的に の対称行列 が与えられて、順列 のうち、
の最小値を求める問題ということになる。 という制約がいかにも bit DP っぽい。というわけで
- dp[ S ] := 順列のうち S の部分集合の並びを最初に決めたときの、その部分で発生するスコア
としたくなる。しかしこのままだと上手く遷移できない。S に新たに要素 a を追加するとき、S の内部の並びがわからないと、それらと a との距離がわからないからだ。そこで少しだけ DP の考え方を変えて、
- S にすでに入っている要素 a について、他の各要素 v に対して、v が S に追加されない限り S の更新において を加算し続ける。
という風にする。計算量は に。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long INF = 1LL<<60; int K; string S; long long solve() { vector<vector<long long> > num(K, vector<long long>(K, 0)); for (int i = 0; i + 1 < S.size(); ++i) { if (S[i] == S[i+1]) continue; int a = S[i] - 'a'; int b = S[i+1] - 'a'; num[a][b]++; num[b][a]++; } vector<long long> dp((1<<K) + 10, INF); dp[0] = 0; for (int bit = 0; bit < (1<<K); ++bit) { int bit2 = (1<<K)-1 - bit; long long cost = 0; for (int i = 0; i < K; ++i) { if (!(bit & (1<<i))) continue; for (int j = 0; j < K; ++j) { if (bit & (1<<j)) continue; cost += num[i][j]; } } for (int v = 0; v < K; ++v) { if (bit & (1<<v)) continue; chmin(dp[bit | (1<<v)], dp[bit] + cost); } } return dp[(1<<K)-1]; } int main() { int SN; while (cin >> SN >> K >> S) { cout << solve() << endl; } }