状压dp， dp[u][s][d] 表示集合为 s ，胜者为u，高度不超过 d 的方案数。转移的时候枚举u所在的集合。 注意记录状态的时候需要记录高度，因为只要求保证总高度最小，并不要求局部最小。
#include<cstdio> #include<algorithm> using namespace std; int map[20][20],dp[16][66000][6],vis[16][66000][6],dep[]={0,1,2,3,3,4,4,4,4,5,5,5,5,5,5,5,5},n,m,clo; int dfs(int u,int s,int sz,int d) { if (vis[u][s][d]==clo) return dp[u][s][d]; vis[u][s][d]=clo; dp[u][s][d]=0; if (sz==1) { dp[u][s][d]=1; return dp[u][s][d]; } int cnt; for (int s1=s&(s-1);s1;s1=s&(s1-1)) { if (!(s1&(1<<u))) continue; cnt=0; for (int i=0;i<n;i++) if (s1&(1<<i)) cnt++; if (max(dep[cnt],dep[sz-cnt])+1>d) continue; for (int i=0;i<n;i++) if (((s^s1)&(1<<i))&&map[u][i]) dp[u][s][d]+=dfs(u,s1,cnt,d-1)*dfs(i,s^s1,sz-cnt,d-1); } return dp[u][s][d]; } void solve() { clo++; for (int i=0;i<n;i++) for (int j=0;j<n;j++) scanf("%d",&map[i][j]); printf("%d\n",dfs(m-1,(1<<n)-1,n,dep[n])); } int main() { //freopen("d.in","r",stdin); while (scanf("%d%d",&n,&m)==2) solve(); }