2010年1月14日星期四.pku3254 狀態壓縮動態規劃
pku3254:狀態壓縮動態規劃
題目給出了一個m*n(m,n<=12)的矩陣，1代表此點可以放玉米，0代表不可放
求 最后可能的放置方案有多少種?
題目中給出了一個例子
2 3
1 1 1
0 1 0
對于這個例子，放置的方法一共有9種
這個題相對于1185 炮兵陣地來說要好做一些，只要記錄上一行的狀態，就可以了，不用記錄
上上行的狀態。
方法也是先枚舉出一行中的所有可行狀態。
然后根據這些可行狀態按行遞推，中間還要記得判斷狀態是否和地形不沖突。
注意運算符的優先級，按照以下形式寫成的宏定義會比較安全
#define bin(i) (1 << (i))
#define L(i) ((i) << 1)
#define R(i) ((i) >> 1)
const int N = 13;
int f[N][bin(N)];
int full,s[bin(N)],top,m,n,terrain[N];
bool contradict(int x)
{
return x & L(x);
}
bool sameRow(int a,int b)
{
return (a&b);
}
void preproc()
{
int i;
for(i = 0;i <= full;i++) {
if(!contradict(i)) {
s[top++] = i;
}
}
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
full = bin(m) - 1;
preproc();
for (i = 1;i <= n;i++) {
int tmp = 0;
for (j = 1;j <= m;j++) {
scanf("%d",&k);
tmp = L(tmp) + (1 - k);
}
terrain[i] = tmp;
}
f[0][0] = 1;
for(i = 1;i <= n;i++) {
for(j = 0;j < top;j++) {
if(s[j] & terrain[i]) continue;
for(k = 0;k < top;k++) {
if(!sameRow(s[j],s[k])) {
f[i][j] =(f[i][j] + f[i-1][k])%100000000;
}
}
}
}
//http://www.shnenglu.com/schindlerlee
int res = 0;
for(i = 0;i < top;i++) {
res =(res + f[n][i])%100000000;
}
cout << res << endl;
return 0;
}