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

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

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

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

#include
#include
#include
#include
#include
#include
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 505
using 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