我终于会这个 dp 了...
0 表示当前行向下覆盖, 1 表示被当前行横着覆盖或者被上一行覆盖
状压, 判断合法状态
没了
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #include<queue>
- #include<stack>
- #include<cmath>
- using namespace std;
- typedef long long ll;
- const int maxn = 12;
- int n,m,a[maxn];
- ll dp[2][1<<maxn];
- bool check(int x){
- int cnt=0;
- while(x) a[++cnt]=(x&1),x>>=1;
- for(int i=1;i<=cnt;++i){
- if(!a[i]) continue;
- if(i<cnt&&a[i+1]==1) ++i;
- else return 0;
- }
- return 1;
- }
- ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}
- int main(){
- while(1){
- n=read(),m=read();
- if((!n)&&(!m)) break;
- memset(dp,0,sizeof(dp));
- int mm=(1<<m)-1;
- dp[0][mm]=1; int now=1;
- for(int i=1;i<=n;++i,now^=1){
- memset(dp[now],0,sizeof(dp[now]));
- for(int j=0;j<=mm;++j){
- for(int k=0;k<=mm;++k){
- if((j|k)==mm){
- int tmp=(j&k);
- if(check(tmp)){
- dp[now][k]+=dp[now^1][j];
- }
- }
- }
- }
- }
- printf("%lld\n",dp[now^1][(1<<m)-1]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2969225.html