HDOJ 2442 -bricks 六进制状态压缩DP 一直TLE.打表过的..

HDOJ 2442 -bricks 六进制状态压缩DP 一直TLE.打表过的..

有5个砖块..加上一个空着不放..那么有6种状态..所以很明显的可以用6进制的状态DP...

不过这么做..我觉得我已经能优化的都优化了...还是超时..一看数据范围是100*6..打表先AC了..

看有大神用3进制状态DP水过..Orz...看了好久没看懂...觉得自己状态DP还是很表面~~

Program:

#include#include#include#include#include#include#define oo 1000000007#define ll long long#define pi acos(-1.0)#define MAXN 505using namespace std;int sharp[6][6][2]={{{0,0},{0,0},{0,0},{0,0},{0,0}}, {{0,0},{1,0},{1,1},{2,0},{-1,-1}}, {{0,1},{1,0},{1,1},{1,2},{2,1}}, {{0,0},{0,1},{0,2},{1,1},{-1,-1}}, {{0,0},{0,1},{0,2},{1,0},{-1,-1}}, {{0,0},{0,1},{1,0},{2,0},{-1,-1}} };int n,m,canuse[132],w[132],tall[132],dp[101][132][132],num,step[6]={0,4,5,4,4,4};bool f[132][132][2];bool legal(int x) // 判断这一行这么安排是否合法{ int i,j,t=x,a[10][10]; memset(a,0,sizeof(a)); w[num+1]=0; for (i=1;i<=m;i++) { if (i+1>m && (x%6==1 || x%6==5)) return false; if (i+2>m && (x%6==2 || x%6==3 || x%6==4)) return false; for (j=0;j1) return false; tall[num+1]=0; for (i=1;i<=m;i++) { if (t%6==1 || t%6==2 || t%6==5) tall[num+1]=2; else if (t%6!=0 && tall[num+1]<1) tall[num+1]=1; t/=6; } return true;} bool ok(int a,int b,int tp) //判断是否冲突{ int i,j,h[10][10]; a=canuse[a],b=canuse[b]; memset(h,0,sizeof(h)); for (i=1;i<=m;i++) { for (j=0;j1) return false; return true;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int r,i,j,x,ans,totol; while (~scanf("%d%d",&n,&m)) { totol=1; for (i=1;i<=m;i++) totol*=6; num=0; for (i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。