首页 > ACM题库 > HDU-杭电 > HDU 4363-Draw and paint-动态规划-[解题报告]HOJ
2015
05-23

HDU 4363-Draw and paint-动态规划-[解题报告]HOJ

Draw and paint

问题描述 :

Shadow is interested in the four-color theorem, now he wants to draw some lines on a rectangle paper to divide it into some parts, and then paint these parts with four different colors, the color of two adjacent parts must be different.
Firstly, Shadow draws a horizontal line and divides the paper into two parts (The height and width of two parts must be integer), then he paints one part with a kind of color.
Then he draws a vertical line and divides the other part into two parts (The height and width of two parts must be integer), then he paints one part with a kind of color.
Then he draws a horizontal line……That is to say, Shadow draws a horizontal line during an odd step, and a vertical line during an even step. Shadow repeats these operations until he can’t or doesn’t want to anymore.
Shadow can’t rotate or overturn the paper, do you know how many different ways can he draw lines and paint colors.

输入:

The first line is one integer T indicates the number of test cases. (T <= 1000)
Then for each test case, there are two integers n and m ( 0 < n,m <= 40 )in one line, indicates the height and width of the rectangle paper.

输出:

The first line is one integer T indicates the number of test cases. (T <= 1000)
Then for each test case, there are two integers n and m ( 0 < n,m <= 40 )in one line, indicates the height and width of the rectangle paper.

样例输入:

3
1 1
1 2
2 1

样例输出:

4
4
16

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents          
by—cxlove

题目:一张纸,轮流在纸上选择一块画横线和竖线,分为两块,将一块染色,问最终纸上颜色情况有多少种。

http://acm.hdu.edu.cn/listproblem.php?vol=1

感谢zz_1215的指导

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里面已经统计过了。

首先对于不能再切的情况,就是枚举4种颜色了。

否则枚举切的位置以及颜色。当切了一刀之后,分为两块,两块的颜色可能一样,这样就重复了,这里需要减掉。

而且还要把整块的颜色都相同的加上。

记忆化搜索。。。总觉得在写法在可以优化,尝试了好多次,总是有细节处理不好,哎

#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\n",get_dp(x,y,0,0,0,0,0));
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7870546