HDOJ 2442 -bricks 狀態壓縮DP 一直TLE.打表過的..

   有5個磚塊..加上一個空著不放..那麼有6種狀態..所以很明顯的可以用6進制的狀態DP...

    不過這麼做..我覺得我已經能優化的都優化了...還是超時..一看數據范圍是100*6..打表先AC了..

    看有大神用3進制狀態DP水過..Orz...看了好久沒看懂...覺得自己狀態DP還是很表面~~

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>
#include<cmath>
#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;j<step[x%6];j++)
               a[sharp[x%6][j][0]][i+sharp[x%6][j][1]-1]++;
            w[num+1]+=step[x%6];
            x/=6;
      }
      for (i=0;i<10;i++)
         for (j=0;j<10;j++)
           if (a[i][j]>1) 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;j<step[a%6];j++) 
                h[sharp[a%6][j][0]][i+sharp[a%6][j][1]-1]++;
             a/=6;
      }
      for (i=1;i<=m;i++)
      {
             for (j=0;j<step[b%6];j++) 
                h[sharp[b%6][j][0]-tp][i+sharp[b%6][j][1]-1]++;
             b/=6;          
      }
      for (i=0;i<10;i++)
         for (j=0;j<10;j++)
           if (h[i][j]>1) 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<totol;i++)
              if (legal(i)) canuse[++num]=i; 
           memset(dp,0,sizeof(dp));
           memset(f,true,sizeof(f));
           for (i=1;i<=num;i++)
             for (j=1;j<=num;j++)
               for (x=1;x<=2;x++)
                 f[i][j][x]=ok(i,j,x);
           for (r=1;r<=n;r++)
              for (i=1;i<=num;i++)
                if (tall[i]+r<=n) 
                  for (j=1;j<=num;j++)
                    if (f[i][j][1])
                       for (x=1;x<=num;x++)
                         if (f[i][x][2]) 
                           dp[r][j][i]=max(dp[r][j][i],dp[r-1][x][j]+w[i]);
 
           ans=0;
           for (i=1;i<=num;i++) ans=max(ans,dp[n][i][1]);
           printf("%d,",ans);
      } 
      return 0;
}