本文主要是介绍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;
}这篇关于CF 937 G. Shuffling Songs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
