poj1038--bugs.cpp

经典的状态DP难题

#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表示的是当前一个和上一格均不放

 一定注意：状态的压缩的表示是以格子是否放置的情况进行考虑的,而不是考虑物品（方块）放置的方式有哪几种（此题中就有两种），
但是确是因为放置方式的增加导致了进制的改变，切记！！！*/