【POJ】1038 Bugs Integrated, Inc.

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<algorithm>
  5 #define MAXN 160
  6 #define MAXM 20
  7 #define MAXL 280
  8 using namespace std;
  9 int n,m;
 10 bool land[MAXN][MAXM];
 11 int put[MAXL][MAXM],cnt[MAXL],tmp[MAXM],size;
 12 vector<int>G[MAXL];
 13 int dp[2][MAXL][MAXL];
 14 bool OK()
 15 {
 16     int i,j,k,res;
 17     for(i=res=0;i<m;i++)
 18     {
 19         if(tmp[i])
 20         {
 21             for(j=i;j<m&&tmp[i]==tmp[j];j++);
 22             k=j-i;
 23             if(tmp[i]==1)
 24             {
 25                 if(k%3)
 26                     return false;
 27                 res+=k/3;
 28             }
 29             else
 30             {
 31                 if(k&1)
 32                     return false;
 33                 res+=k>>1;
 34             }
 35             i=j-1;
 36         }
 37     }
 38     cnt[size]=res;
 39     return true;
 40 }
 41 void DFS(int now)
 42 {
 43     if(now==m)
 44     {
 45         if(OK())
 46             memcpy(put[size++],tmp,sizeof(tmp));
 47     }
 48     else
 49     {
 50         int i;
 51         for(i=0;i<3;i++)
 52         {
 53             tmp[now]=i;
 54             DFS(now+1);
 55         }
 56     }
 57 }
 58 bool Upper(int x,int y)
 59 {
 60     int i;
 61     for(i=0;i<m;i++)
 62     {
 63         if(put[x][i]&&put[y][i])
 64             return false;
 65     }
 66     return true;
 67 }
 68 void Init()
 69 {
 70     int i,j;
 71     size=0;
 72     memset(land,false,sizeof(land));
 73     memset(dp,0,sizeof(dp));
 74     DFS(0);
 75     for(i=0;i<size;i++)
 76     {
 77         G[i].clear();
 78         for(j=0;j<size;j++)
 79         {
 80             if(Upper(i,j))
 81                 G[i].push_back(j);
 82         }
 83     }
 84 }
 85 bool Unfit(int r,int x)
 86 {
 87     int i;
 88     for(i=0;i<m;i++)
 89     {
 90         if(land[r][i]&&put[x][i])
 91             return true;
 92     }
 93     return false;
 94 }
 95 bool First(int x)
 96 {
 97     int i;
 98     for(i=0;i<m;i++)
 99     {
100         if(put[x][i]==2||put[x][i]&&land[1][i])
101             return true;
102     }
103     return false;
104 }
105 bool Three(int x,int y,int k)
106 {
107     int i;
108     for(i=0;i<m;i++)
109     {
110         if(put[x][i]==2)
111         {
112             if(put[y][i]||land[k][i])
113                 return true;
114         }
115     }
116     return false;
117 }
118 void DoIt()
119 {
120     int i,j,k,t,x,y,ans;
121     for(ans=i=0;i<size;i++)
122     {
123         if(Unfit(2,i)||First(i))
124             continue;
125         dp[0][i][0]=cnt[i];
126     }
127     for(i=3;i<=n;i++)
128     {
129         for(j=0;j<size;j++)
130         {
131             if(Unfit(i,j))
132                 continue;
133             for(k=0;k<G[j].size();k++)
134             {
135                 x=G[j][k];
136                 if(Unfit(i-1,x)||Unfit(i-1,j))
137                     continue;
138                 for(t=0;t<G[x].size();t++)
139                 {
140                     y=G[x][t];
141                     if(Unfit(i-2,y)||Unfit(i-2,x)||Three(j,y,i-2))
142                         continue;
143                     dp[i&1][j][x]=max(dp[i&1][j][x],dp[(i-1)&1][x][y]+cnt[j]);
144                 }
145                 ans=max(ans,dp[i&1][j][x]);
146             }
147         }
148     }
149     printf("%d\n",ans);
150 }
151 int main()
152 {
153     int c,q,x,y;
154     scanf("%d",&c);
155     while(c--)
156     {
157         scanf("%d%d%d",&n,&m,&q);
158         Init();
159         while(q--)
160         {
161             scanf("%d%d",&x,&y);
162             land[x][y-1]=true;
163         }
164         DoIt();
165     }
166     return 0;
167 }