AOJ 0537 : Bingo

問題リンク：Bingo | Aizu Online Judge

解法：
動的計画法を行う
問題の制約より、N*Nのマスを全て異なる数で総和がSになるような状態の数を求めれば良い亊がわかる

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MOD 100000

using namespace std;

int N,M,S;
int dp[50][3001];

int main()
{
  while(scanf("%d %d %d",&N,&M,&S),N|M|S)
    {

      rep(i,N*N+1)rep(j,S+1)dp[i][j] = 0;
      dp[0][0] = 1;

      for(int v=1;v<=M;v++)
	{
	  for(int cnt=N*N-1;cnt>=0;cnt--)
	    {
	      for(int def=0;def<=S;def++)
		{
		  if(dp[cnt][def] == 0)continue;
		  if(def+v <= S)
		    {
		      dp[cnt+1][def+v] = (dp[cnt+1][def+v] + dp[cnt][def]) % MOD;
		    }
		}
	    }
	}
      printf("%d\n",dp[N*N][S]);
    }
  return 0;
}

||

*1385996219*[POJ][動的計画法] POJ 3254 : Corn Fields
問題リンク：[http://poj.org/problem?id=3254:title]

問題概要：
H*Wの1と0からなるグリッドが与えられる
自分は１の部分にコーンを植えることができる
ただし、そのマスにコーンを植える際にはそのマスの上下左右にはコーンがあってはならない
コーンの植え方は何通り存在するのか？

解法：
bitDPを行う
今見ているセル(x,y)より前のW個のセルの状態をビットとしてもつ
つまり、以下のグリッドの'o'を今見ているセル(x,y)とすると、

....
.o..

以下の'x'の部分をビットとしてもつ
.xxx
xo..

これをグリッドの左上から今いるマスより前のW個が条件に違反しない様にしながら埋めていく
こうする亊で今いるマスより先は考えなくてすむ
今いるセルの上と左以外のセルの状態は気にする必要はない（条件に違反している場合要素が0になっているので影響しない）

コード：
>|c|
#include<cstdio>
#include<iostream>
#include<bitset>
#include<cmath>
#include<algorithm>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MOD 100000000

using namespace std;

int H,W;
int field[13][13];
int dp[2][(1<<12)];

int main()
{
  scanf("%d %d",&H,&W);
  rep(i,H)rep(j,W)scanf("%d",&field[i][j]);

  rep(i,2)rep(j,(1<<12))dp[i][j] = 0;
  dp[0][0] = 1;

  rep(y,H)rep(x,W)
    {
      rep(state,(1<<W))
	{
	  int next_state = (state<<1) & ((1<<W)-1);
	  dp[(x+y*W+1)&1][next_state] = (dp[(x+y*W+1)&1][next_state]+dp[(x+y*W)&1][state]) % MOD;  

	  if(!field[y][x])continue;

	  if((state>>(W-1)) & 1)continue;
	  if(x)
	    {
	      if((state>>0)&1)continue;
	      dp[(x+y*W+1)&1][next_state|1] = (dp[(x+y*W+1)&1][next_state|1]+dp[(x+y*W)&1][state]) % MOD;
	    }
	  else
	    {
	      dp[(x+y*W+1)&1][next_state|1] = (dp[(x+y*W+1)&1][next_state|1]+dp[(x+y*W)&1][state]) % MOD;
	    }
	}
      rep(i,(1<<W))dp[(x+y*W)&1][i] = 0;
    }

  int ans = 0;
  rep(i,(1<<W))ans = (ans + dp[(H*W)&1][i]) % MOD;
  printf("%d\n",ans);

  return 0;
}