转载请注明出处,谢谢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;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦