CF 937 G. Shuffling Songs

原题链接：Problem - G - Codeforces

题目大意：t组数据，每组数据给出n个歌曲，歌曲由二维构成，第一维为类型，第二维为作者，如果二首歌曲类型相同或者作者相同，那么它们就可以连续播放，题目中给出的音乐顺序可以改变，问删除多少首歌曲之后连续播放的音乐最多？

思路：状压dp+dfs，可以观察到一组数据最多只能给出16首音乐，可以用一个数的二进制来表示这个歌曲选和不选，那么就可以想到使用状压dp来求解这一题，首先dp数组第一维要用来表示选择歌曲的情况，但是歌曲排列的顺序会影响连续播放音乐的长度，那么就可以加一个维度，来表示当前选择的歌曲是以哪一首结尾的。遍历给出的音乐，以当前的音乐为第一首去进行dfs搜索能够和当前音乐接上的音乐然后更新dp的值，可以想到能够直接相连的歌曲在题目给出的时候就已经确定了，那么就可以先预处理出当前歌曲可以和那些歌曲相连接来减少dfs次数。最后遍历整个dp数组来找到能相连的最大值。

//冷静，冷静，冷静
//调不出来就重构 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld; 
typedef pair<ll,ll> pii;
const int N=1e6+10;
ll h[N],e[N],ne[N],idx;
string s[20],v[20];
bool dp[70000][20];
void add(ll a,ll b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(ll state,ll now)
{
	if(dp[state][now])return;dp[state][now]=1;//dfs，如果当前搜过了那么就直接返回 
	for(ll i=h[now];~i;i=ne[i])//遍历now这个点能够直接相连的点 
	{
		ll j=e[i];
		if(state&(1<<j))continue;//如果这个点存在状态排列里面了就没必要继续搜索 
		ll nxt_state=state|(1<<j);//这是新的状态 
		dfs(nxt_state,j);
	}
}
ll calc(ll x)
{
	ll sum=0;
	while(x)
	{
		sum=sum+(x%2);
		x/=2;
	}
	return sum;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll t;cin>>t;
	while(t--)
	{
		ll n;cin>>n;
		idx=0;
		for(int i=0;i<n;i++)//读入歌曲的二个维度 
		{
			cin>>s[i]>>v[i];
			h[i]=-1;
		}
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				if(s[i]==s[j]||v[i]==v[j])//作者相同或者类型相同那么就可以相连接 
				{
					add(i,j);
					add(j,i);
				}
			}
		}
		for(int i=0;i<(1<<n);i++)//多组数据，每次都要情空 
		{
			for(int j=0;j<n;j++)
			{
				dp[i][j]=0;
			}
		}
		for(int i=0;i<n;i++)//让当前歌曲当第一首去dfs，搜索出能够以当前歌曲为第一首的所有排列 
		{
			dfs(1<<i,i);
		}
		ll mx=0;
		for(int i=0;i<(1<<n);i++)
		{
			for(int j=0;j<n;j++)
			{
				if(dp[i][j])
				{
					mx=max(mx,calc(i));//如果这个排列存在，那么就寻找最大值 
				}
			}
		}
		cout<<n-mx<<endl;
	}
    return 0;
}