poj1038--Bugs.rar_Bugs_poj 1038 _poj10_poj1038

#include<iostream> using namespace std; const int NUM=59050; const int N=151; const int M=11; int value[4][NUM]; int num,carry[M],bit[M][NUM]; int main() { int d,m,n,bug,input[N][M],blank[M]; int r1,r2; int s1,s2; int now,one,two,three; int i,j,k,t,r,result,ans; bool c1,c2; scanf("%d",&d); carry[0]=1; for(i=1;i<M;i++) carry[i]=carry[i-1]*3; for(i=0;i<carry[M-1];i++) for(t=i,r=1;t>0;t/=3,r++) bit[r][i]=t%3; while(d--!=0) { scanf("%d %d %d",&n,&m,&bug); //cin>>n>>m>>bug; memset(value,0,sizeof(value)); ans=0; num=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) input[i][j]=1; for(i=1;i<=bug;i++) { scanf("%d %d",&r1,&r2); // cin>>r1>>r2; input[r1][r2]=0; } for(i=1;i<=m;i++) blank[i]=input[1][i]; for(i=2;i<=n;i++) { for(j=0;j<m;j++) { now=((i-2)*m+j)%4; one=(now+3)%4; two=(now+2)%4; three=(now+1)%4; if(input[i][j+1]) blank[j+1]++; else blank[j+1]=0; s1=2*(carry[j]+carry[j-1]); s2=carry[j]+carry[j-1]+carry[j-2]; c1=(blank[j+1]>1&&blank[j]>1&&blank[j-1]>1); c2=(i>=3&&blank[j+1]>2&&blank[j]>2); for(k=0;k<carry[m];k++) { if(bit[j+1][k]!=0) value[now][k]=value[one][k-carry[j]]; else { value[now][k]=value[one][k]; if(j>=1&&bit[j][k]==0) if(c2==1) //if(i>2&&input[i][j+1]==1&&input[i][j]==1&&input[i-1][j+1]==1&&input[i-1][j]==1&&input[i-2][j+1]==1&&input[i-2][j]==1) { result=value[two][k+s1]+1; if(value[now][k]<result) value[now][k]=result; //if(ans<result) // ans=result; } if(j>=2&&bit[j][k]==0&&bit[j-1][k]==0) if(c1==1) //if(input[i][j+1]==1&&input[i][j]==1&&input[i][j-1]==1&&input[i-1][j+1]==1&&input[i-1][j]==1&&input[i-1][j-1]==1) { result=value[three][k+s2]+1; if(value[now][k]<result) value[now][k]=result; // if(ans<result) // ans=result; } } } } } printf("%d\n",value[now][0]); //cout<<ans<<endl; //cout<<value[now][0]<<endl; } return 0; } /*在状态压缩中，0代表的是上一格和上两格放；1代表的是上两格不放，但是上一格放；2代表的是上一格不放。 now,one,two,three是一种横向的处理，而三进制表示当前格的放置状态是一种纵向的处理 将其与炮兵阵地进行对比，同样是可是向上延伸三格，为什么炮兵阵地用的是二进制，而此题用的是三进制呢？ 真正的原因是此题的方块它是可以既能2*3，也能3*2的，也就是说如果规定方块只能用3*2或2*3的放置，同样可以只用二进制方法来进行解决， 以3*2为例：此时0表示当前一个不放，1表示的是当前一个和上一格均不放 一定注意：状态的压缩的表示是以格子是否放置的情况进行考虑的,而不是考虑物品（方块）放置的方式有哪几种（此题中就有两种）， 但是确是因为放置方式的增加导致了进制的改变，切记！！！*/