首页 > 代码库 > SGU-448 Controlled Tournament ( 状态DP )
SGU-448 Controlled Tournament ( 状态DP )
输入比赛人员个数 N 和你希望赢的人的编号 M,
然后输入 N * N 的输赢表,第 i 行 第 j 列为 1,代表 i 能赢 j。
求 M 最后能赢,且总比赛树的最小高度时,一共有多少种可能。
比如输入:
7 2
0 1 0 0 0 1 0
0 0 1 0 1 1 1
1 0 0 1 1 0 0
1 1 0 0 0 1 0
1 0 0 1 0 0 1
0 0 1 0 1 0 0
1 0 1 1 0 1 0
则输出:
139
#include <iostream> #include <vector> #include <cstring> #include <cmath> using namespace std; vector< int > wins_table[16]; int DP[16][20][1 << 16]; int one_in_bits_[1 << 16]; int dfs_search( int root, int height, int set_bits ){ if( one_in_bits_[set_bits] == 1 ) return 1; if( ( 1 << height ) < one_in_bits_[set_bits] ) return 0; if( DP[root][height][set_bits] != -1 ) return DP[root][height][set_bits]; else DP[root][height][set_bits] = 0; for( int set1 = set_bits & ( set_bits - 1 ); set1; set1 = set_bits & ( set1 - 1 ) ){ if( ( set1 >> root ) & 1 ){ int set2 = set1 ^ set_bits; for( int i = 0; i < wins_table[root].size(); ++i ){ int other = wins_table[root][i]; if( ( set2 >> other ) & 1 ){ DP[root][height][set_bits] += dfs_search( root, height - 1, set1 ) * dfs_search( other, height - 1, set2 ); } } } } return DP[root][height][set_bits]; } int main(){ for( int i = 0; i < ( 1 << 16 ) - 1; ++i ) one_in_bits_[i] = one_in_bits_[i >> 1] + ( i & 1 ); int players, winner; while( cin >> players >> winner ){ memset( DP, -1, sizeof( DP ) ); for( int i = 0; i < players; ++i ){ wins_table[i].clear(); for( int j = 0; j < players; ++j ){ int win; cin >> win; if( win ) wins_table[i].push_back( j ); } } int height = ceil( log( players ) / log( 2 ) ); int ans = dfs_search( winner - 1, height, ( 1 << players ) - 1 ); cout << ans << endl; } return 0; }
思路:
DP[root][height][set] 代表 以 root 为根,比赛树高度为 height 时,已经比赛过人员集合为 set 时的可能性
则 DP[root][height][set] = ∑ ( DP[root][height - 1][set1] * DP[other][height - 1][set - set1] )
SGU-448 Controlled Tournament ( 状态DP )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。