[동적 기획] [Uva11270]Tiling Dominoes

4287 단어 동태
이 문제는 바로 연결성 상태 압축 DP입니다. 복습해 봤습니다.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
long long dp[11][11][(1<<11)+1][2], n, m;
long long dfs(int x, int y, int md, int right){
    long long &ret = dp[x][y][md][right];
    if(ret != -1) return ret;
    if(x >= n){
        if(!md) return ret = 1;
        else return ret = 0;
    }
    if(y >= m){
        if(right) return ret = 0;
        else return ret = dfs(x+1, 0, md, 0);
    }
    ret = 0;
    int now_Pos = 1 << y;
    if(right){
        if(md & now_Pos) return ret = 0;
        return ret = dfs(x, y+1, md, 0);
    }
    if(md & now_Pos){
        int n_md = md ^ now_Pos;
        return ret = dfs(x, y+1, n_md, right);
    }
    int n_md = md | now_Pos;
    return ret =( y+1 < m ? dfs(x, y+1, md, 1) : 0 )+ dfs(x, y+1, n_md, 0);
}
int main(){
    while(scanf("%d %d", &n, &m)!=EOF){
        if(n == 1 || m == 1){
            if((n % 2)^(m % 2))
                cout<<1<<endl;
            else cout<<0<<endl;
            continue;
        }
        memset(dp, -1, sizeof dp);
        cout<<dfs(0, 0, 0, 0)<<endl;
    }
}

이 문제는 만약 귀속 버전의 요TLE를 쓴다면 왠지 모르겠지만 나는 아직 A가 없다

좋은 웹페이지 즐겨찾기