Eight Digital Games Gym - 102623E（建图，枚举排列）

本文主要是介绍Eight Digital Games Gym - 102623E（建图，枚举排列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Setsuna has been obsessed with an electronic video game called “Eight Digital”. It is a puzzle game which is too difficult for Setsuna, so she has been stuck in the first level for a long time.

In the game, you have a string of length 𝑛 containing only digits from 1 to 8. Let’s call this string 𝑆, 𝑆𝑖 denotes the 𝑖-th character of 𝑆.

At the end of the game, the game system will calculate the penalties of inversions, and will deduct your coins. Inversion is a pair (𝑖,𝑗) which satisfies both 𝑖<𝑗 and 𝑆𝑖>𝑆𝑗. The game system will deduct you 𝑃𝑆𝑖,𝑆𝑗 coins for each inversion (𝑖,𝑗).

For example, string 85511 will cost you 2×𝑃8,5+2×𝑃8,1+4×𝑃5,1 coins, and string 1234 will cost you 0 coins.

Before the end of the game, you can do arbitrary times of the operation. Each operation is to select two different numbers 𝑥 and 𝑦(1≤𝑥,𝑦≤8), then all 𝑥 in the string will become 𝑦, and all 𝑦 will become 𝑥 and the game system will deduct you 𝐶𝑥,𝑦 coins.

For example, you can spend 𝐶1,3 to convert string 131233 into string 313211.

To help poor girl Setsuna, you are required to find the minimum cost of coins to finish the game.

Input
The first line contains one integer 𝑛(1≤𝑛≤105).

The second line contains a string 𝑆. It is guaranteed that the length of 𝑆 is 𝑛 and 𝑆 only contains digits from 1 to 8.

The next 8 lines contains 8 integers each, where the 𝑗-th integer of the 𝑖-th line is 𝑃𝑖,𝑗(0≤𝑃𝑖,𝑗≤107). It is guaranteed that 𝑃𝑖,𝑗=0 holds for 𝑖≤𝑗.

The next 8 lines contains 8 integers each, where the 𝑗-th integer of the 𝑖-th line is 𝐶𝑖,𝑗(0≤𝐶𝑖,𝑗≤1012). It is guaranteed that 𝐶𝑖,𝑖=0 and 𝐶𝑖,𝑗=𝐶𝑗,𝑖.

Output
Output one integer indicating the minimum cost.

Examples
inputCopy
5
54321
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0
outputCopy
2
inputCopy
6
222112
0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
0 1 2 2 2 2 2 2
1 0 2 2 2 2 2 2
2 2 0 2 2 2 2 2
2 2 2 0 2 2 2 2
2 2 2 2 0 2 2 2
2 2 2 2 2 0 2 2
2 2 2 2 2 2 0 2
2 2 2 2 2 2 2 0
outputCopy
4
Note
In sample 1, you can spend 1 coin to convert 54321 into 14325. Then, spend another 1 coin to convert it into 12345.

In sample 2, you can spend 2 coins to convert 222112 into 222882, then end the game. The inversions (4,6) and (5,6) will cost you 2×𝑃8,2=2 coins. So the total cost is 4 coins.

题意：
只由1~8组成的序列，不同的逆序对会产生一定的花费。你可以用一定的花费将两种数字全部交换。求产生的最小花费。

思路：
参考博客：https://blog.csdn.net/ECNU_SF/article/details/106584769

我觉得关键点就在于怎么操作的花费和操作完毕后逆序对的花费。

首先是操作的花费：
本题中的操作可以抽象为两个排列的映射。
如1 2 3 4 5 6 7 8映射到4 3 2 5 1 7 8 6，
那么(2,1)就变成了(4,3)，(4,5)就变成了(5,1)，以此类推。

我们可以将排列当做点，那么排列间的变换就是边，跑一遍最短路就知道排列（也就是操作）的花费了。

然后是逆序对的花费：
我们维护 $d p [i] [j]$ 代表数对 $(i, j)$ 的个数，
那么操作完成之后，数对 $(i, j)$ 会映射成 $(n u m [i], n u m [j])$ ，对应的花费就是 $d p [i] [j] * P [n u m [i]] [n u m [j]]$ 。

几个tips：

排列的编号怎么求：最直接的想法就是把排列当成8位数字，然后枚举一遍全排列再映射一下。看了题解发现，是有组合数学的方法（就是下面的perm2num函数）。
关于排列之间怎么建边：交换两个位置, $C [i] [j]$ 和 $C [a [i]] [a [j]]$ 的边权都是可以的。前者是逆序变化，后者是顺序变化。

#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>using namespace std;
typedef long long ll;const int maxn = 1e6 + 7;
const int mod = 998244353;ll d[maxn],P[10][10],C[10][10],dp[10][10];
int fac[10],cnt[maxn],vis[maxn];char s[maxn];struct Node {int a[10];ll cost;bool operator < (const Node &res) const {return cost > res.cost;}
};int perm2num(int* a) {int res = 0;for(int i = 1; i < 8; i++) {int cnt = 0;for(int j = i + 1; j <= 8; j++)if(a[i] > a[j])cnt++;res += cnt * fac[8 - i];}return res;
}void dijkstra() {priority_queue<Node>q;Node fir;for(int i = 1;i <= 8;i++) {fir.a[i] = i;}fir.cost = 0;q.push(fir);memset(d,0x3f,sizeof(d));d[perm2num(fir.a)] = 0;while(!q.empty()) {Node now = q.top();q.pop();int x = perm2num(now.a);if(vis[x]) continue;vis[x] = 1;Node nex = now;for(int i = 1;i <= 8;i++) {for(int j = i + 1;j <= 8;j++) {if(i == j) continue;swap(nex.a[i],nex.a[j]);int y = perm2num(nex.a);if(d[y] > d[x] + C[nex.a[i]][nex.a[j]]) {d[y] = d[x] + C[nex.a[i]][nex.a[j]];nex.cost = d[y];q.push(nex);}swap(nex.a[i],nex.a[j]);}}}
}int main() {fac[0] = 1;for(int i = 1;i <= 8;i++) {fac[i] = fac[i - 1] * i;}int n;scanf("%d",&n);scanf("%s",s + 1);for(int i = 1;i <= 8;i++) {for(int j = 1;j <= 8;j++) {scanf("%lld",&P[i][j]);}}for(int i = 1;i <= 8;i++) {for(int j = 1;j <= 8;j++) {scanf("%lld",&C[i][j]);}}for(int i = 1;i <= n;i++) {int now = s[i] - '0';for(int j = 1;j <= 8;j++) {dp[j][now] += cnt[j];}cnt[now]++;}dijkstra();int num[10] = {0,1,2,3,4,5,6,7,8};ll ans = 1e18;do {int idx = perm2num(num);ll res = d[idx];for(int i = 1;i <= 8;i++) {for(int j = 1;j <= 8;j++) {res += dp[i][j] * P[num[i]][num[j]];}}ans = min(ans,res);}while(next_permutation(num + 1,num + 1 + 8));printf("%lld\n",ans);return 0;
}