HDU 4363 Draw and paint (DP)

전재 출처 를 밝 혀 주 십시오.감사합니다. http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove
제목:종이 한 장,돌아 가면 서 종이 에 가로줄 과 세로 줄 을 그 려 두 조각 으로 나 누 어 한 조각 을 염색 하고 최종 종이 의 색깔 상황 이 몇 가지 인지 물 어 본다.
http://acm.hdu.edu.cn/listproblem.php?vol=1
감사합니다 zz1215 의 지도
7 차원 DP 는 사실 6 차원 까지 최적화 할 수 있다.가로 자 르 기와 세로 자 르 는 관 계 는 회전 한 후에 자 르 는 것 이다.
dp[x][y][l][r][u][d][k]는 길이 가 x,y,위,아래,왼쪽,오른쪽 색상 이 각각 l,r,u,d 일 때의 염색 종 수 를 나타 내 며 경계 색상 과 주변 이 같 을 수 없습니다.우 리 는 4 가지 색깔 을 1,2,3,4 로 표시 하고 빈 흰색 을 0 으로 한다.K 가 0 일 때 는 다음 가로 자 르 기,K 가 1 일 때 는 다음 세로 자 르 기 를 나타 낸다.
1*1 로 염색 할 것 이 있 으 면 위 에 빨간색 이 있 으 면 여 기 는 빨간색 으로 염색 할 수 없다 는 뜻 이다.2*1 에 통 계 된 것 이기 때문이다.
우선 더 이상 자 를 수 없 는 경우 에는 네 가지 색깔 을 매 거 하 는 것 이다.
그렇지 않 으 면 매 거 진 위치 와 색상.한 칼 을 자 른 후에 두 조각 으로 나 뉘 었 는데 두 조각의 색깔 이 같 을 수 있 습 니 다.이렇게 반복 되 었 습 니 다.여 기 는 빼 야 합 니 다.
그리고 전체 색깔 을 똑 같이 더 해 야 돼 요.
기억 화 검색...아무래도 쓰 는 방법 이 최적화 되 고 여러 번 시도 해 봤 는데 디 테 일이 잘 처리 되 지 않 는 것 같 아 요.

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1<<29
#define LL long long
#define MOD 1000000007
using namespace std;
int dp[41][41][5][5][5][5][2];
int get_dp(int x,int y,int l,int r,int u,int d,int k){
    if(dp[x][y][l][r][u][d][k]!=-1)
        return dp[x][y][l][r][u][d][k];
    dp[x][y][l][r][u][d][k]=0;
    //         
    if((x==1&&k==0)||(y==1&&k)){
        for(int i=1;i<5;i++)
           if(i!=l&&i!=r&&i!=u&&i!=d)
               dp[x][y][l][r][u][d][k]++;
        return dp[x][y][l][r][u][d][k];
    }
    dp[x][y][l][r][u][d][k]=0;
    if(!k){
        for(int i=1;i<x;i++)
            for(int j=1;j<5;j++){
                if(j!=u&&j!=l&&j!=r)
                    dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(x-i,y,l,r,j,d,1))%MOD;
                if(j!=d&&j!=l&&j!=r)
                    dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(i,y,l,r,u,j,1))%MOD;
            }
        // t     ，      x-1 
        int t=0;
        for(int i=1;i<=4;i++)
            if(i!=u&&i!=l&&i!=r)
                for(int j=1;j<=4;j++)
                    if(j!=d&&j!=l&&j!=r&&j!=i)
                       t++;
        dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+MOD-t*(x-1))%MOD;
        //        
        for(int i=1;i<5;i++)
            if(i!=l&&i!=r&&i!=u&&i!=d)
                dp[x][y][l][r][u][d][k]++;
    }
    else{
        for(int i=1;i<y;i++)
            for(int j=1;j<5;j++){
                if(j!=l&&j!=d&&j!=u)
                    dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(x,y-i,j,r,u,d,0))%MOD;
                if(j!=r&&j!=d&&j!=u)
                    dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(x,i,l,j,u,d,0))%MOD;
            }
        int t=0;
        for(int i=1;i<=4;i++)
            if(i!=l&&i!=u&&i!=d)
                for(int j=1;j<=4;j++)
                   if(j!=r&&j!=u&&j!=d&&j!=i)
                      t++;
        dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+MOD-t*(y-1))%MOD;
        for(int i=1;i<5;i++)
            if(i!=l&&i!=r&&i!=u&&i!=d)
                dp[x][y][l][r][u][d][k]++;
    }
    return dp[x][y][l][r][u][d][k]%MOD;
}
int main(){
    memset(dp,-1,sizeof(dp));
    int t;
    scanf("%d",&t);
    while(t--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d
",get_dp(x,y,0,0,0,0,0));
    }
    return 0;
}