Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## O(2^w*h*w*w) 的算法

Posted by yrjie at 2014-09-06 17:15:16 on Problem 2411
```把第i行状态分成两类,一类是没有打横的,一类是有打横的,没有打横的根据i-1来进行dp,有打横的根据当前行来进行dp

#include <stdio.h>
#include <cstring>

#define MAXN 11

int h, w;
__int64 dp1[MAXN][1<<MAXN], dp2[MAXN][1<<MAXN][MAXN], ans;
bool flag;

bool inSt(int i, int s){
return ((1<<i)&s)>0;
}

int main(){
int S, i, j, k, s, now;
while (1){
scanf("%d%d",&h,&w);
if (h==0&&w==0) break;
S=(1<<w)-1;
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
dp1[0][0]=1;
for (i=0;i<h;i++){
for (s=0;s<=S;s++){
if (i>0){
now=S;
for (j=0;j<w;j++)
if (inSt(j,s)) now-=(1<<j);
dp1[i][s]+=dp1[i-1][now];
for (j=0;j<w;j++)
dp1[i][s]+=dp2[i-1][now][j];
}
for (j=0;j<w-1;j++){
if (inSt(j,s)&&inSt(j+1,s)){
now=s-(1<<j)-(1<<(j+1));
dp2[i][s][j]+=dp1[i][now];
for (k=0;k<j-1;k++){
dp2[i][s][j]+=dp2[i][now][k];
}
}
}
}
}
ans=dp1[h-1][S];
for (i=0;i<w;i++)
ans+=dp2[h-1][S][i];
printf("%I64d\n",ans);
}
return 0;
}```

Followed by: