poj 1038 Bugs Integrated, Inc.

题目链接：http://poj.org/problem?id=1038

题目解析黑书139,很好的题。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int dp[60000][2];
int pre[12],cur[12],p[12],mp[160][12];
int t,n,m,k,tmp;
void init()
{
    p[0]=1;
    for(int i=1;i<12;i++)
    {
        p[i]=p[i-1]*3;
    }
}
void turn(int state)
{
   for(int i=0;i<m;i++)
   {
       pre[i]=state%3;
       state/=3;
   }
}
int getstate(int a[])
{
    int i,s;
    s=0;
    for(i=0;i<m;i++)
        s+=a[i]*p[i];
    return s;
}
void dfs(int row,int i,int cnt,int s)
{
    int now;
    if(i+2<m&&cur[i]==0&&cur[i+1]==0&&cur[i+2]==0)
    {
        now=s+2*p[i]+2*p[i+1]+2*p[i+2];
        dp[now][1-tmp]=max(dp[now][1-tmp],cnt+1);
      //  printf("row %d now %d i %d dp %I64d\n",row,now,i,dp[now][1-tmp]);
        if(i+3<m);
            dfs(row,i+3,cnt+1,now);
    }
    if(i+1<m&&cur[i]==0&&cur[i+1]==0&&pre[i]==0&&pre[i+1]==0)
    {
        now=s+2*p[i]+2*p[i+1];
        dp[now][1-tmp]=max(dp[now][1-tmp],cnt+1);
        if(i+2<m)
            dfs(row,i+2,cnt+1,now);
    }

    now=s;
    dp[now][1-tmp]=max(dp[now][1-tmp],cnt);
    if(i+1<m)
    {
        dfs(row,i+1,cnt,now);
    }

}
int main()
{
    int x,y,state,i,j,l;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(mp,0,sizeof(mp));
        while(k--)
        {
            scanf("%d%d",&x,&y);
            mp[x][y]=1;
        }

        memset(dp,-1,sizeof(dp));
            state=0;
        state=p[m]-1;
        dp[state][0]=0;
        tmp=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<=state;j++)
                dp[j][1-tmp]=-1;
            for(j=0;j<=state;j++)
            {

                if(dp[j][tmp]!=-1)
                {
                    turn(j);
                    for(l=1;l<=m;l++)
                    {
                        if(mp[i+1][l])
                            cur[l-1]=2;
                        else if(pre[l-1]>0)
                            cur[l-1]=pre[l-1]-1;
                        else
                            cur[l-1]=0;
                    }
                    dfs(i+1,0,dp[j][tmp],getstate(cur));
                }
            }
            tmp=1-tmp;
        }
        int ans=0;
        for(i=0;i<=state;i++)
        {
            ans=max(ans,dp[i][tmp]);
        }
        printf("%d\n",ans);
    }
    return 0;
}