hihoCoder 1170 机器人 (状压dp)

63 阅读 0 评论 42 点赞

我是靠谱客的博主唠叨跳跳糖，最近开发中收集的这篇文章主要介绍hihoCoder 1170 机器人 (状压dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

有16种颜色的球，现在有n个这样的球排成一列，要求将这些球变成所有相同颜色必须在一起的状态，每次只能交换相邻的球。

题解：

这题的做法并不知道如何解释，只是意会了而已。

预处理出每种颜色的球变换到其他颜色的球前面对应的步数，事实上这个步数是相对某个状态来说的。然后就是状态压缩，每次添加一种颜色的球进去。

注意：预处理也是有技巧的，暴力必然超时。

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#define B(x) (1<<(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int oo = 0x3f3f3f3f;
const ll OO = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define lson rt<<1
#define rson rt<<1|1
void cmax(int& a, int b){ if (b > a)a = b; }
void cmin(int& a, int b){ if (b < a)a = b; }
void cmax(ll& a, ll b){ if (b > a)a = b; }
void cmin(ll& a, ll b){ if (b < a)a = b; }
void cmax(double& a, double b){ if (a - b < eps) a = b; }
void cmin(double& a, double b){ if (b - a < eps) a = b; }
void add(int& a, int b, int mod){ a = (a + b) % mod; }
void add(ll& a, ll b, ll mod){ a = (a + b) % mod; }
const int MOD = 100007;
const int maxn = 110000;
ll dp[B(17)], cost[20][20];
vector<int>id[20];

void Init(int n){
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (i == j) continue;
			int sum = 0;
			int t = 0;
			for (int k = 0; k < id[i].size(); k++){
				while (t < id[j].size() && id[j][t] < id[i][k])t++;
				sum += t;
			}
			cost[i - 1][j - 1] = sum;
		}
	}
}

int main(){
	//freopen("E:\read.txt", "r", stdin);
	int T, n, k, a, full, cas = 1;
	scanf("%d", &T);
	while (T--){
		scanf("%d %d", &n, &k);
		for (int i = 1; i <= k; i++)id[i].clear();
		for (int i = 1; i <= n; i++){
			scanf("%d", &a);
			id[a].push_back(i);
		}
		Init(k);
		full = B(k) - 1;
		for (int s = 0; s <= full; s++)dp[s] = OO;
		dp[0] = 0;
		for (int s = 0; s <= full; s++){
			if (dp[s] == OO) continue;
			for (int i = 0; i < k; i++){
				if (s&B(i)) continue;
				ll sum = 0;
				for (int j = 0; j < k; j++){
					if (i == j)continue;
					if (!(s&B(j)))continue;
					sum += cost[i][j];
				}
				cmin(dp[s | B(i)], dp[s] + sum);
			}
		}
		printf("Case #%d: %lldn", cas++, dp[full]);
	}
	return 0;
}