1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 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 ]
/**************************************************************
Problem: 1087
User: shadowland
Language: C++
Result: Accepted
Time:40 ms
Memory:6336 kb
****************************************************************/ #include "bits/stdc++.h" using namespace std ;
const int maxNum = ;
const int maxN = ; bool feasible[ maxNum << ] , feasible_flat[ maxNum << ][ maxNum << ] ;
long long f[ maxN ][ ][ maxNum ] , num[ maxNum << ] ; long long Ans ; inline bool Check ( const int x , const int y ) {
if ( ( ( x & y ) == ) && ( ( x & ( y >> ) ) == ) && ( ( x & ( y << ) ) == ) ) return true ;
else return false ;
} void Init ( const int N , const int M ) {
int _cnt = ;
for ( int i= ; i<=( << N ) - ; ++i ) {
if ( ( i & ( i << ) ) == ) {//状态合法记录
_cnt = ;
for ( int Base = i ; Base ; Base >>= ) _cnt += ( Base & ) ;
num[ i ] = _cnt ;//
feasible[ i ] = true ;
}
}
for ( int i= ; i<=( << N ) - ; ++i ) {
if ( feasible[ i ] ) {
for ( int j= ; j<=( << N ) - ; ++j ) {
if ( feasible[ j ] ) {
if ( Check ( i , j ) ) {
feasible_flat[ i ][ j ] = true ;
}
}
}
}
}
} void DEBUG_( int n , int m ) {
printf ( "\n" ) ;
for ( int i= ; i<=( << n ) - ; ++i )
printf ( "%d " , feasible[ i ] ) ; printf ( "\n" ) ;
for ( int i= ; i<=( << n ) - ; ++i ) {
for ( int j= ; j<=( << n ) - ; ++j ) {
printf ( "%d " , feasible_flat[ i ][ j ] ) ;
}
printf ( "\n" ) ;
}
} void DEBUG___( int n , int m ) {
for ( int i= ; i<=n ; ++i ) {
for ( int j= ; j<=( << n ) - ; ++j ) {
for ( int k= ; k<= ( << n ) - ; ++k ) {
printf ( "%d ",f[i][j][k]);
}
}
}
}
int main ( ) {
int N , M ;
scanf ( "%d %d" , &N , &M ) ;
Init( N , M ) ;
for ( int i= ; i<=( << N ) - ; ++i ) {//第一行的所有合法状态
if ( feasible[ i ] ) {
f[ ][ num[ i ] ][ i ] = ;
}
}
for ( int j = ; j<N ; ++j ) {
for ( int x = ; x<= ( << N ) - ; ++x ) {
if ( feasible[ x ] ) {//x状态合法
for ( int y= ; y<= ( << N ) - ; ++y ) {
if ( feasible[ y ] ) {//y状态合法
if ( feasible_flat[ x ][ y ] ) {
for ( int p=num[ x ] ; p + num[ y ] <=M ; ++p ) {
f[ j + ][ p + num[ y ] ][ y ] += f[ j ][ p ][ x ] ;
}
}
}
}
}
}
}
//DEBUG_( N , M ) ;
//DEBUG___( N , M ) ;
for ( int i= ; i<= ( << N ) - ; ++i ) {
Ans += f[ N ][ M ][ i ] ;//统计最终合法状态
}
cout << Ans << endl ;
return ;
}
一定要开long long 。不开long long 见祖宗，十年OI一场空。
2016-10-12 23:20:05
(完)