题意：一串数字变成另一串数字，可以单个数字转变，或者一类数字转变，问最少操作次数
分析：首先一类转换比单个转换优，先枚举找出最优的映射方案，然后将零碎的操作加上。6位6进制表示map映射，比如123456，表示map[1] = 1, map[2] = 2, map[3] = 3…
先预处理出每种方案的的操作数，用BFS+dp写，然后暴力枚举取最小值。
#include <bits/stdc++.h>
using namespace std;const int N = 110 + 5;
const int M = 5e4 + 5;
const int INF = 0x3f3f3f3f;
char ori[N], fin[N];
int dp[M];
int cnt[6];
int g[6][6];int idx(int *c){
int ret = 0;
for (int i=0; i<6; ++i){
ret = ret * 6 + c[i];
}
return ret;
}void ridx(int x, int *c){
for (int i=5; i>=0; --i){
c[i] = x % 6;
x /= 6;
}
}void BFS(void){
memset (dp, INF, sizeof (dp));
int c[6];
for (int i=0; i<6; ++i)c[i] = i;//nomal, not change
int s = idx (c);dp[s] = 0;
queue<int> que;que.push (s);
while (!que.empty ()){
int u = que.front ();que.pop ();
ridx (u, c);
for (int i=0; i<6; ++i){
for (int j=0; j<6; ++j){
int t[6];
memcpy (t, c, sizeof (t));
for (int k=0; k<6; ++k){
if (t[k] == i)t[k] = j;
}
int v = idx (t);
if (dp[v] > dp[u] + 1){
dp[v] = dp[u] + 1;
que.push (v);
}
}
}
}
}int main(void){
BFS ();
while (scanf ("%s%s", ori, fin) == 2){
int len = strlen (ori);
memset (cnt, 0, sizeof (cnt));
memset (g, 0, sizeof (g));
for (int i=0; i<len; ++i){
int d1 = fin[i] - '1', d2 = ori[i] - '1';
cnt[d1]++;g[d1][d2]++;
}
int ans = INF;
int c[6];
for (int i=0; i<M; ++i){
ridx (i, c);
int tmp = dp[i];
for (int j=0; j<6; ++j){
tmp += cnt[j] - g[j][c[j]];
}
ans = min (ans, tmp);
}
printf ("%d\n", ans);
}return 0;
}
/*
22345611
12345611
2234562221
1234561221
2234562211
1234561111
22345622112
12345611111
654321654321654321654321
123456123456123456123456
*/
