hoj 2662


大概題意是：有一個n*m的棋盤，在這個棋盤里邊放k個旗子，要求每一行每一列都不能存在一對旗子相鄰，問最后總共的方案數。


這道題一看狀態非常多，就一定是狀壓。怎么狀壓呢？這又是個問題。
慢慢考慮下這道題每個局面分別有哪些狀態，我們很容易就能想到有以下幾個狀態：
第一：每一行放了多少個旗子；
第二：已經用了多少個旗子;
第三：已經放的這些旗子能不能保證合法，即上下左右均不相鄰。
在這里可能還不容易想到那個狀態表達式，那么我們先來考慮個簡單的，假如說只有一行，要求在這一行里邊填充k個旗子，要求任意兩個都不相鄰，這個時候的dp應該怎么表示?這就很簡單了，直接就是dp[i][j][x]，代表已經到了第i列，已經使用了j個旗子，而且當前第i列的狀態就是x（當然這里x只能是0和1,這里0代表這個第i列沒有放旗子，1就代表這個位置放了旗子）的總方案數，遞推關系是怎么寫？其實也很簡單，
dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
dp[i][j][1]=dp[i-1][j-1][0];//這里只能是dp[i-1][j-1][0]，因為第i列已經放了，那么第i-1列就一定不能放。
當然這里你需要考慮到二維的局面，怎么考慮，把行對應于列，每一列的狀態轉化為每一行的狀態，前i列使用了j個旗子變成前i行使用了j個旗子就這樣思考。
綜上考慮，我們會想到要有一個這樣的dp，就是dp[i][j][x]，這里代表的是：
填充旗子已經填到第i行了，已經使用了j個旗子，而且當前第i行的狀態就是x的這么一個
表示前i行的總方案數。
那么遞推怎么推？
dp[i][j][x]+=dp[i-1][j-num(mark[x])][y];
解釋一下，這里的x是當前第i行的狀態，而這個mark[x]代表當前狀態下的十進制表示，也就是說把一個狀態表示成十進制之后就是mark[x]了，這里為什么是j-num(mark[x])呢？因為啊，你這樣想。反過來推。如果你在前i-1行已經使用了j-num(mark[x])個旗子，而且num(mark[x])就代表第i行你使用的旗子，那么你在前i行是不是就使用了j個旗子？
就這樣逆推。這個mark[x]和mark[y]分那別代表第i行和第i-1行的狀態的十進制表示。
最后你只要把dp[n][k][i]其中i是從0到最多狀態的那些狀態，把他們加起來。

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#include<cmath>  
#include<algorithm>  
#include<cstdlib>  using namespace std;  long long n,m,k,dp[82][22][1<<9],ans,mm;//dp[i][j][x]第i行放了j個棋子當前狀態為x時的方法數  
long long mark[1<<9],len;//十進制標記每一行的狀態  using namespace std;  long long num(long long x) //記錄狀態x中1的個數  
{  long long sum=0;  while(x)  {  if(x&1)  sum++;  x=x>>1;  }  return sum;  
}  bool judge(long long x) //判斷狀態x是否有相鄰的棋子放在一起  
{  if(x&(x<<1)) return false;  return true;  
}  int main()  
{  while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF)  {  ans=0;  memset(dp,0,sizeof(dp));  memset(mark,0,sizeof(mark));  len = 0;  long long tmpp = n > m ? n : m;  m = n > m ? m : n; //m為小的數  n = tmpp;//n為大的數計為行  for(long long i=0;i<(1<<m);i++) //初始化第一行的放置方法數//剔除不合法狀態  if(judge(i)) //若i狀態沒有相鄰的棋子放在一起  {  dp[1][num(i)][len]=1;//則第一行狀態為len（i）時1的個數為num（i）時的方法數  mark[len ++] = i;//標記狀態             }  for(long long i=2;i<=n;i++) //第二行到第n行  for(long long j=0;j<=k;j++)//對于放0***n個棋子  for(long long x = 0 ; x < len ; x ++) //對于0***len-1個狀態（第i行）//枚舉  {  for(long long y = 0 ; y < len ; y ++)//對于0***len-1個狀態（第i-1行）//枚舉  {  long long tmp = num (mark[x]);//第i行狀態x中1的個數  if(((mark[x] & mark[y]) == 0 ) && j >= tmp) //若上下2行沒相鄰的且當前的棋子數目大于此行當前狀態所用的棋子  dp[i][j][x] += dp[i - 1][j - tmp][y];//放法數可相加  //到當前行共用了j個棋子，當前行用了tmp個棋子，狀態為x，到上一行共用了j-tmp個棋子，狀態為y  }  }  for(long long i=0;i< len;i++) //枚舉狀態相加  ans += dp[n][k][i];  printf("%lld\n",ans);  }  return 0;  
} 

總結

以上是生活随笔為你收集整理的状态压缩dp(hdu2662)(我综合了一个人的解释和另一个人的代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。