这个是一个状压dp
题目大意是:给你一个数组,数组的数在1到20之间,有一个操作就是交换相邻的两个数,问 让所有相同的数相邻的最小操作次数
dp[s] 表示s状态下的操作次数,w[i][j] 表示 i 前面 j 的个数,c[i] 表示一开始使 i 放到最前面的最小操作次数。
val[s][i] 表示在s状态下,将 i 放到前面的操作次数。
那么dp[tmp]=min(dp[tmp],dp[s]+val[s][j])
#include <cstdio> #include <cstring> #include <cstdlib> #include <queue> #include <string> #include <algorithm> #include <iostream> #include <map> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 4e5 + 10; typedef long long ll; vector<int>num; ll dp[1 << 20], c[21]; ll w[21][21], val[1 << 20][21]; int vis[21], b[21], a[maxn], sum[21]; bool vit[21]; void judge(int x) { num.clear(); for (int i = 1; x; i++) { if (x & 1) num.push_back(i); x >>= 1; } } int main() { int n, len = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (!vit[a[i]]) b[++len] = a[i]; vit[a[i]] = 1; } sort(b + 1, b + 1 + len); for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b; for (int i = 1; i <= n; i++) { sum[a[i]]++; for (int j = 1; j <= len; j++) { if (j == a[i]) continue; w[a[i]][j] += sum[j]; } } memset(dp, inf64, sizeof(dp)); for (int i = 1; i <= n; i++) { c[a[i]] += i - 1 - vis[a[i]]; vis[a[i]]++; } for (int i = 1; i <= len; i++) dp[1 << (i - 1)] = c[i]; for (int i = 0; i < (1 << len); i++) { judge(i); for (int j = 1; j <= len; j++) { ll x = c[j]; int tmp = 1 << (j - 1); if ((tmp | i) == i) continue; for (int k = 0; k < num.size(); k++) x -= w[j][num[k]]; val[i][j] = x; } } for (int i = 0; i < (1 << len); i++) { for (int j = 1; j <= len; j++) { int tmp1 = 1 << (j - 1); if ((tmp1 | i) == i) continue; if (dp[i] >= inf64) continue; tmp1 |= i; dp[tmp1] = min(dp[tmp1], dp[i] + val[i][j]); } } printf("%lld\n", dp[(1 << len) - 1]); return 0; }
原文:https://www.cnblogs.com/EchoZQN/p/11574052.html