题意：
N名选手淘汰赛，要求指定的选手M夺冠。给定胜负关系矩阵，Aij=1，代表选手 i 能够战胜选手 j 。要求比赛树的高度尽量小，求所有可能的方案总数
分析：
这个树的高度尽量小很坑很坑，要怎么理解！
树高尽量小是前提，然后才是选手M夺冠
意味着，当N给定时，树的高度已经限定了，因为是淘汰赛，所以当N<=2时，树高h=1
2<N<=4时，h=2。5<N<=8时，h=3。8<N<=16时，h=4！
这里的树高尽量小，是为了解释样例：
4 1
0 0 0 1
1 0 0 1
1 1 0 0
0 0 1 0N=4，h=2
所以，我们无法构造一棵比赛树使得选手1夺冠
但是，如果没有树高这个限制，我们可以构造出：1 - 4 - 3 - 2
意思是：3与2比赛淘汰2，4与3比赛淘汰3，1与4比赛淘汰4，最终1夺冠~但是不符合树高的条件
根据N的大小，明显是二进制的状态压缩动态规划
定义：dp[i][h][S]为最终获胜为选手 i，树高度为h，选手集合为S的方案总数
我们需要解决几个问题：
A：状态转移方程
我们枚举每一个 i 可以获胜的选手 j，那么可以把选手集合分成S1和S2，使得S1 + S2 = S，S1 | S2 = 0
其中 i in S1，j in S2，S1和S2枚举一个，剩下一个计算并检查
那么，就得到了dp的状态转移（实际在写的时候，这里还是有坑，稍后说明）
B：记忆化搜索的初始化问题
边界条件：什么时候不合法，什么时候是边界（看记忆化搜索的return部分很清楚）
细节部分1：
如何枚举S1和S2：
int set_bits = 13;
for( int set1 = set_bits & ( set_bits - 1 ); set1; set1 = set_bits & ( set1 - 1 ) ){
int set2 = set1 ^ set_bits;
printf("%d %d\n",set1,set2);
}
printf("-------------\n");
set_bits = 13;
for(int i = 1; i < set_bits; i++){
int j = set_bits - i;
if (((i & j) == 0)&&((i | j) == set_bits))
printf("%d %d\n",i,j);
}给出对比的样例代码，上面是题解的代码，下面是我的枚举代码，虽然结果相同，但是不是一个数量级的枚举
上面的每次操作得到的都是合法的S1和S2，但是下面的枚举还得检查S1和S2的集合关系，所以导致超时
细节部分2：
如何枚举每一个 i 可以获胜的选手 j
for(int l=0;l<mp[i].size();l++){
int j=mp[i][l];
//
}
printf("--------\n");
for(int j=0;j<n;j++)
if (mp[i][j]){
//
}这里靠的是输入输出的数据变形能力了，题目中给的是胜负关系矩阵，如果对于每个i，都枚举任意j，然后查看胜负关系矩阵，那么是下面的for循环写法；但是，如果输入的时候判断一次选手 i 可以战胜哪些选手 j，只保留这些 i 可以赢的，那么就是写法1，毫无疑问，写法1更优
细节部分3：
高度h的计算：
int h = ceil( log( n ) / log( 2 ) );
printf("--------\n");
int h=0;
int number=1;
while(number<n){
number*=2;
h++;
}
printf("--------\n");
int h=0;
int div=n;
while(div){
h++;
div/=2;
}
这里只有写法3是错的，因为当n是2的幂次时，h会比正确值大1~~~
解释清楚了细节，贴两份代码：
//ac
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;
const int maxn=17;
int n,m;
int dp[maxn][6][1<<maxn];
int mp[maxn][maxn];
int cnt[1<<maxn];
int GETdp(int i,int h,int S){
if (dp[i][h][S]!=-1) return dp[i][h][S];
if (S==(1<<i)) return dp[i][h][S]=1;
if ((1<<h) < cnt[S]) return dp[i][h][S]=0;
dp[i][h][S]=0;
for(int set1=S&(S-1);set1;set1=S&(set1-1)){
if (set1&(1<<i)){
int set2=set1^S;
for(int j=0;j<n;j++)
if (mp[i][j] && (set2 & (1<<j)))
dp[i][h][S] += GETdp(i,h-1,set1) * GETdp(j,h-1,set2);
}
}
return dp[i][h][S];
}
int main(){
//freopen("input.txt","r",stdin);
for( int i = 0; i < ( 1 << 16 ) - 1; ++i )
cnt[i] = cnt[i >> 1] + ( i & 1 );
scanf("%d%d",&n,&m);
m--;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&mp[i][j]);
memset(dp,-1,sizeof(dp));
int h = int(ceil( log( n ) / log( 2 ) ));
GETdp(m,h,(1<<n)-1);
if (dp[m][h][(1<<n)-1]==-1) dp[m][h][(1<<n)-1]=0;
printf("%d\n",dp[m][h][(1<<n)-1]);
return 0;
}
下面这个是超时代码，仅仅是枚举的姿势不一样（导致了很多无用值和无用判断）
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=17;
int n,m;
int dp[maxn][6][1<<maxn];
int cnt[1<<maxn];
vector< int > mp[maxn];
int GETdp(int i,int h,int S){
if (dp[i][h][S]!=-1) return dp[i][h][S];
if (S==(1<<i)) return dp[i][h][S]=1;
if ((1<<h) < cnt[S]) return dp[i][h][S]=0;
dp[i][h][S]=0;
for(int l=0;l<mp[i].size();l++){
int j=mp[i][l];
if (S&(1<<j))
for(int k=(1<<i);k<=S-(1<<j);k++){
if (((k & (S-k)) == 0) && ((k | (S - k)) == S))
if ((k & (1<<i)) && ((S-k) & (1<<j))){
dp[i][h][S] += GETdp(i,h-1,k) * GETdp(j,h-1,S-k);
}
}
}
/*
for(int set1=S&(S-1);set1;set1=S&(set1-1)){
if (set1&(1<<i)){
int set2=set1^S;
//for(int j=0;j<n;j++)
for(int l=0;l<mp[i].size();l++){
int j=mp[i][l];
if (set2 & (1<<j))
dp[i][h][S] += GETdp(i,h-1,set1) * GETdp(j,h-1,set2);
}
}
}*/
return dp[i][h][S];
}
int main(){
//freopen("input.txt","r",stdin);
for( int i = 0; i < ( 1 << 16 ) - 1; ++i )
cnt[i] = cnt[i >> 1] + ( i & 1 );
scanf("%d%d",&n,&m);
m--;
int h;
for(int i=0;i<n;i++){
mp[i].clear();
for(int j=0;j<n;j++){
scanf("%d",&h);
if (h)
mp[i].push_back(j);
}
}
memset(dp,-1,sizeof(dp));
h = int(ceil( log( n ) / log( 2 ) ));
GETdp(m,h,(1<<n)-1);
if (dp[m][h][(1<<n)-1]==-1) dp[m][h][(1<<n)-1]=0;
printf("%d\n",dp[m][h][(1<<n)-1]);
return 0;
}
京公网安备 11010502036488号