题解 [ABC236D] Dance

cjh20090318 · 2024-01-19 23:21:52 · 题解

简单搜索题。

题意

将 2N 个人两两分组，每两个人配对会有一个快乐值，求快乐值异或最大。

分析

观察数据范围 N \le 8，很容易想到搜索。

又因为 2N \le 16，所以直接枚举全排列不可行，需要做一点优化。

第 i 个人和第 j 个人配对产生的快乐值，与第 j 个人和第 i 个人配对产生的快乐值是一样的。所以不妨设 i < j，可以减少掉冗余的 i>j 的状态。

然后做上面这个剪枝就行了。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[20][20];
bool vis[20];//标记是否已经配对。
int ans=0;
void dfs(const int pos,const int w){
    if(pos>n){ans=max(ans,w);return;}//更新答案。
    if(vis[pos]){dfs(pos+1,w);return;}//当前如果已经配对，枚举下一个。
    vis[pos]=1;
    for(int i=pos+1;i<=n;i++)if(!vis[i]) vis[i]=1,dfs(pos+1,w^a[pos][i]),vis[i]=0;//寻找配对的伙伴。
    vis[pos]=0;//注意标记清零。
}
int main(){
    scanf("%d",&n),n<<=1;
    for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++) scanf("%d",&a[i][j]);
    dfs(1,0),printf("%d\n",ans);
    return 0;
}