poj 1038 Bugs Integrated, Inc. 题解
- 2021 年 1 月 25 日
- 笔记
提供一种代码难度比较简单的做法(可能)
状态表示：
设置状态$ f[i][j] $,表示第 \(i\) 行状态为 \(j\) 的最大放置数,因为这是个阴间题,因为题目内存设置很小，所以要用滚动数组，存储两行的状态就够了。
状态用三进制表示：
0 表示当前行和上一行均可用
1 表示当前行可用，上一行不可用
2 表示当前行和上一行都不可用
为了方便不过常数确实略大,我们用两个数组 \(pre\) , \(now\) 分别存放上一行和当前行的状态
那么就有:
inline int getstate(int a[])//存放状态
{
int temp=0;
for(register int i=1;i<=m;i++)
temp+=a[i]*t[i];
return temp;
}
inline int getstring(int temp,int*a)//取出状态
{
for(register int i=1;i<=m;i++)
{
a[i]=temp%3;
temp/=3;
}
}
判断放矩形(设要放矩形的左下角为 (i,j) )：
横放：
state(i,j)=0 且 state(i,j+1)=0 且 state(i,j+2)=0 \(\ \ \ \ (j+2 \le m\),废话\()\)
竖放：
state(i,j)=0 且 state(i,j+1)=0 且 state(i-1,j)=0 且 state(i-1,j+1)==0 \(\ \ \ (j+1 \le m\),二度废话\()\)
DP过程:
显然,当我们知道第i行状态，和第i-1行初始状态时，就可以愉快地DP了。
因为状态转换略显复杂写成循环的话可能需要很多层，所以可以用大法师\(DFS\)来写。
设置dfs参数分别为，试图放置的坐标，放置矩形的数量，第\(i\)行状态:
如果足横放，竖放，不放的情况，分别搜一下就行。
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,k,D;
int mp[151][15];
int f[2][59050];//f[i][j] i是滚动数组，j存放状态
int now[15],pre[15],t[15];//pre为i-1行，now为第i行
//0 表示当前行和上一行均可用
//1 表示当前行可用，上一行不可用
//2 表示当前行和上一行都不可用
inline int qr()
{
char a=0;int w=1,x=0;
while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
return x*w;
}
inline int getstate(int a[])//存放状态
{
int temp=0;
for(register int i=1;i<=m;i++)
temp+=a[i]*t[i];
return temp;
}
inline int getstring(int temp,int*a)//取出状态
{
for(register int i=1;i<=m;i++)
{
a[i]=temp%3;
temp/=3;
}
}
void dfs(int i,int j,int num,int state)//(i,j)为尝试放矩形的右下角位置，num为放矩形数量，state为第i行状态
{
f[i%2][state]=max(f[i%2][state],num);//更新最大值
int k;
if(j>=m)
return ;
if(j<m-1&&now[j]==0&&now[j+1]==0&&now[j+2]==0)//这一行加上一行能横放一个
{
now[j]=now[j+1]=now[j+2]=2;
k=getstate(now);
dfs(i,j+3,num+1,k);
now[j]=now[j+1]=now[j+2]=0;
}
if(j<m&&pre[j]==0&&pre[j+1]==0&&now[j]==0&&now[j+1]==0)//这一行和上两行能竖放一个
{
now[j]=now[j+1]=2;
k=getstate(now);
dfs(i,j+2,num+1,k);
now[j]=now[j+1]=0;
}
dfs(i,j+1,num,state);//不放矩形
}
int main()
{
D=qr();
t[1]=1;
for(register int i=2;i<=11;i++)
t[i]=t[i-1]*3;
while(D--)
{
n=qr();
m=qr();
k=qr();
memset(mp,0,sizeof(mp));
while(k--)
mp[qr()][qr()]=1;
for(register int i=0;i<t[m+1];i++)
f[1][i]=-1;
for(register int i=1;i<=m;i++)//第一行的上一行无法利用
pre[i]=mp[1][i]+1;//记录初始状态
int state=getstate(pre);
f[1][state]=0;
for(register int i=2;i<=n;i++)
{
for(register int j=0;j<t[m+1];j++)//预处理第i行状态
f[i%2][j]=-1;
for(register int j=0;j<t[m+1];j++)
{
if(f[(i+1)%2][j]==-1)
continue;
getstring(j,pre);//取出状态j
for(register int k=1;k<=m;k++)
{
if(mp[i][k]==1)//这个块坏了这一行跟上一行都用不了
now[k]=2;
else//块没坏
if(pre[k]==2)//上一行用不了
now[k]=1;//只能用本行
else
now[k]=0;//本行和上一行都能用
}
state=getstate(now);
dfs(i,1,f[(i+1)%2][j],state);//从j状态转移到state状态
}
}
int ans=0;
for(register int i=0;i<t[m+1];i++)//统计答案
ans=max(ans,f[n%2][i]);
printf("%d\n",ans);
}
return 0;
}
