NYOJ 492 King (狀態(tài)壓縮)

做題感悟：做完這題發(fā)現(xiàn)狀態(tài)壓縮有許多需要優(yōu)化的地方。

解題思路：狀態(tài)壓縮

開始自己用的一般的思路，就和炮兵陣地，鄭廠長等題類似的方法做的，開始超時，然后把數(shù)組開到了最小的極限就險過。然后看了別人的代碼感覺需要優(yōu)化（注意）的地方太多了。

首先我們這題可以預(yù)處理出來上下兩行對應(yīng)的合法狀態(tài)，這樣我們就確定下來上下兩行對應(yīng)的狀態(tài)了，這是第一步的優(yōu)化 。因為當(dāng)前行只與上一行有關(guān)（這里只考慮當(dāng)前行對上一行的影響就可以），我們可以把 dp 第一維開成 2 的就可以了，這是第二步的優(yōu)化，雖然這步作用有點(diǎn)小。最后 ，我們還可以拋棄一些不合法的輸入 ，假如是 n * n 的棋盤，一行最多可以防止（n+1）/ 2 個，然后 n 行最多可以放置 ( n + 1 ) / 2 * ( n + 1 ) / 2 個。 為什么是 ( n + 1 ) / 2 行放置呢 ？ 因為每個格子攻擊相鄰的八個格子，不要用n / 2 ,因為如果 奇數(shù)行的話就少算了一行。

這題也可以用DFS遞推和鋪方格差不多，這樣也相當(dāng)于預(yù)處理出上下兩行對應(yīng)的狀態(tài)。

代碼：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std ;

#define INT long long int

#define L(x) (x * 2)

#define R(x) (x * 2 + 1)

const int INF = 0x3f3f3f3f ;

const double esp = 0.0000000001 ;

const double PI = acos(-1.0) ;

const int mod = 1e9 + 7 ;

const int MY = 1400 + 5 ;

const int MX = 150 ;

int n ,m ,num ,top ;

INT dp[2][MX][101] ;

int key[MX] ,h[MX] ;

struct node

{

int x ,y ,c ;

}P[MY] ;

void init() // 預(yù)處理合法狀態(tài)

{

for(int S = 0 ;S < (1<

if(!(S&(S>>1)) && !(S&(S<<1)))

{

int nx = 0 ;

for(int i = 0 ;i < n ; ++i)

if(S&(1<

nx++ ;

key[num] = S ;

h[num++] = nx ;

}

}

int main()

{

while(~scanf("%d%d" ,&n ,&m))

{

if(((n+1)/2)*((n+1)/2) < m) // 拋棄不合法的狀態(tài)

{

puts("0") ;

continue ;

}

num = 0 ; top = 0 ;

init() ; // 預(yù)處理合法狀態(tài)

for(int i = 0 ;i < num ; ++i) // 預(yù)處理上下兩行對應(yīng)的合法狀態(tài)

for(int j = 0 ;j < num ; ++j)

if(!(key[i]&(key[j]>>1)) && !(key[i]&(key[j]<<1)) && !(key[i]&key[j]))

{

P[top].x = i ;

P[top].y = j ;

P[top++].c = h[j] ;

}

memset(dp[0] ,0 ,sizeof(dp[0])) ;

dp[0][0][0] = 1 ;

for(int i = 1 ;i <= n ; ++i)

{

memset(dp[i&1] ,0 ,sizeof(dp[i&1])) ;

for(int j = 0 ;j < top ; ++j) // 上一行的合法狀態(tài)

for(int t = 0 ;t <= m ; ++t) // 安放的個數(shù)

if(t + P[j].c <= m) // 個數(shù)限制

dp[i&1][P[j].y][t+P[j].c] += dp[(i+1)&1][P[j].x][t] ;

}

INT ans = 0 ;

for(int i = 0 ;i < num ; ++i)

ans += dp[n&1][i][m] ;

printf("%lld\n" ,ans) ;

}

return 0 ;

}

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。