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

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

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

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

Program:

#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;
}