首页 > 代码库 > BZOJ 1087 题解【状压DP】
BZOJ 1087 题解【状压DP】
1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3112 Solved: 1816
[Submit][Status][Discuss]
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
HINT
Solution
这是一道状压DP题，本蒟蒻第一次做状压，坑了好久。
我们用0和1代表棋盘上的某点是否放棋子，每一行的状态都可以用唯一的一个十进制数表示，我们可以通过位运算，得到合法状态数，并统计即可。
DP方程：
f[ i + 1 ][ p + num[ y ] ][ y ] += f[ i ][ p ][ x ]
1 /************************************************************** 2 Problem: 1087 3 User: shadowland 4 Language: C++ 5 Result: Accepted 6 Time:40 ms 7 Memory:6336 kb 8 ****************************************************************/ 9 10 #include "bits/stdc++.h" 11 12 using namespace std ; 13 const int maxNum = 512 ; 14 const int maxN = 10 ; 15 16 bool feasible[ maxNum << 2 ] , feasible_flat[ maxNum << 1 ][ maxNum << 1 ] ; 17 long long f[ maxN ][ 100 ][ maxNum ] , num[ maxNum << 2 ] ; 18 19 long long Ans ; 20 21 inline bool Check ( const int x , const int y ) { 22 if ( ( ( x & y ) == 0) && ( ( x & ( y >> 1 ) ) == 0 ) && ( ( x & ( y << 1 ) ) == 0 ) ) return true ; 23 else return false ; 24 } 25 26 void Init ( const int N , const int M ) { 27 int _cnt = 0 ; 28 for ( int i=0 ; i<=( 1 << N ) - 1 ; ++i ) { 29 if ( ( i & ( i << 1 ) ) == 0 ) {//状态合法记录 30 _cnt = 0 ; 31 for ( int Base = i ; Base ; Base >>= 1 ) _cnt += ( Base & 1 ) ; 32 num[ i ] = _cnt ;// 33 feasible[ i ] = true ; 34 } 35 } 36 for ( int i=0 ; i<=( 1 << N ) - 1 ; ++i ) { 37 if ( feasible[ i ] ) { 38 for ( int j=0 ; j<=( 1 << N ) - 1 ; ++j ) { 39 if ( feasible[ j ] ) { 40 if ( Check ( i , j ) ) { 41 feasible_flat[ i ][ j ] = true ; 42 } 43 } 44 } 45 } 46 } 47 } 48 49 void DEBUG_( int n , int m ) { 50 printf ( "\n" ) ; 51 for ( int i=0 ; i<=( 1 << n ) - 1 ; ++i ) 52 printf ( "%d " , feasible[ i ] ) ; 53 54 printf ( "\n" ) ; 55 for ( int i=0 ; i<=( 1 << n ) -1 ; ++i ) { 56 for ( int j=0 ; j<=( 1 << n ) - 1 ; ++j ) { 57 printf ( "%d " , feasible_flat[ i ][ j ] ) ; 58 } 59 printf ( "\n" ) ; 60 } 61 } 62 63 void DEBUG___( int n , int m ) { 64 for ( int i=1 ; i<=n ; ++i ) { 65 for ( int j=0 ; j<=( 1 << n ) - 1 ; ++j ) { 66 for ( int k=0 ; k<= ( 1 << n ) - 1 ; ++k ) { 67 printf ( "%d ",f[i][j][k]); 68 } 69 } 70 } 71 } 72 int main ( ) { 73 int N , M ; 74 scanf ( "%d %d" , &N , &M ) ; 75 Init( N , M ) ; 76 for ( int i=0 ; i<=( 1 << N ) - 1 ; ++i ) {//第一行的所有合法状态 77 if ( feasible[ i ] ) { 78 f[ 1 ][ num[ i ] ][ i ] = 1 ; 79 } 80 } 81 for ( int j = 1 ; j<N ; ++j ) { 82 for ( int x = 0 ; x<= ( 1 << N ) - 1 ; ++x ) { 83 if ( feasible[ x ] ) {//x状态合法 84 for ( int y=0 ; y<= ( 1 << N ) - 1 ; ++y ) { 85 if ( feasible[ y ] ) {//y状态合法 86 if ( feasible_flat[ x ][ y ] ) { 87 for ( int p=num[ x ] ; p + num[ y ] <=M ; ++p ) { 88 f[ j + 1 ][ p + num[ y ] ][ y ] += f[ j ][ p ][ x ] ; 89 } 90 } 91 } 92 } 93 } 94 } 95 } 96 //DEBUG_( N , M ) ; 97 //DEBUG___( N , M ) ; 98 for ( int i=0 ; i<= ( 1 << N ) - 1 ; ++i ) { 99 Ans += f[ N ][ M ][ i ] ;//统计最终合法状态 100 }101 cout << Ans << endl ;102 return 0 ;103 }
2016-10-12 23:20:05
(完)
BZOJ 1087 题解【状压DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。