- Mondriaan's Dream
记忆化搜索
- 2025-6-28 11:12:04 @
#include<bits/stdc++.h>
using namespace std;
long long f[12][1<<11];
long long h,w;
bool check(long long pp){
long long cnt=0;
for(int i=0;i<w;i++){
if(pp&(1<<i)){
if(cnt&1) return false;
cnt=0;
}else cnt++;
}
return (cnt&1)==0;
}
long long dp(long long d,long long pp){
if(d==0)return pp==0;
if(f[d][pp]!=-1)return f[d][pp];
long long ans=0;
for(int i=0;i<(1<<w);i++){
if((i&pp)==0&&check(i|pp)){
ans+=dp(d-1,i);
}
}
return f[d][pp]=ans;
}
long long jg(){
memset(f,-1,sizeof f);
return dp(h,0);
}
int main(){
while(cin>>h>>w){
if(h==0&&w==0)break;
cout<<jg()<<endl;
}
}
0 comments
No comments so far...
Information
- ID
- 405
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 26
- Accepted
- 11
- Uploaded By