poj1038 Bugs Integrated,Inc. (状压dp)

题意:N*M的矩阵,矩阵中有一些坏格子,要在好格子里铺2*3或3*2的地砖,问最多能铺多少个。

我的方法好像和网上流传的方法不太一样...不管了....

由数据范围很容易想到状压dp

我们设某个状态的某一位表示这个格是某种地砖的左上角

那么就会有三种状态,理论上应该用三进制来存储,但我哪会三进制用位运算很方便于是就用2位二进制数来代替1位三进制数...

用00代表没有地砖,01代表铺了个2*3的地砖,10代表铺了个3*2的地砖

然后为了节约空间和时间,先对一个空行dfs一遍,得到这一行可能的地砖铺法,存储下来方便以后枚举状态(M=10时总共有274种状态)

然后设f[i][j][k]为第i行,状态为j,上一行状态为k的地砖数量

然后f[i][j][k]=max{f[i-1][k][l]},枚举k,l,然后判断符合不符合条件即可

为了防止爆内存可以用unsigned char强行卡用滚动数组(我第一次还真是用unsigned char强行卡过的..因为总共数量最多也就10*150/6=250种)

说着轻巧但是好难判啊

然后我不小心输出答案时用了%lld结果一直WA???求解答...

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define inf 0x3f3f3f3f
#define LL long long int
using namespace std;
const int maxm=,maxn=,maxs=;
const int f11=,f01=;
const int b0101=,b101010=,b11=,b1111=,b111111=; inline LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int sta[maxs],fsta[maxs],sct,mp[maxn];
int f[][maxs][maxs];
int N,M,K;char num[maxs]; inline void print(int x,int y){
if(y<=M*-) print(x>>,y+);
printf("%d",x&);
} void dfs(int x,int s,int fs,int c){
if(x>=M){sta[++sct]=s;fsta[sct]=fs;num[sct]=c;return;}
dfs(x+,s,fs,c);
if(x<=M-){
dfs(x+,s|(b0101<<(x<<)),fs|(b1111<<(x<<)),c+);
}if(x<=M-){
dfs(x+,s|(b101010<<(x<<)),fs|(b111111<<(x<<)),c+);
}
} inline bool judge1(int i,int s){
return (s&(mp[i]|mp[i+]))||(s&f01&mp[i+]);
} int main(){
//freopen("1038.in","r",stdin);
int i,j,k,l;
for(int t=rd();t;t--){
N=rd(),M=rd(),K=rd();
memset(mp,,sizeof(mp));
sct=;dfs(,,,);
for(i=;i<=K;i++){
int a=rd(),b=rd();
mp[a-]|=b11<<((b-)<<);
}mp[N+]=mp[N]=f11;
bool b=;
for(i=;i<N-;i++){
memset(f[b],-,sizeof(f[b]));
for(j=;j<=sct;j++){
if(judge1(i,sta[j])) continue;
if(!i){f[b][j][]=num[j];continue;}
for(k=;k<=sct;k++){
if((sta[j]&fsta[k])||judge1(i-,sta[k])) continue;
for(l=;l<=sct;l++){
if(fsta[j]&(sta[l]&f01)) continue;
f[b][j][k]=max(f[b][j][k],f[b^][k][l]);
}if(f[b][j][k]==-) continue;
f[b][j][k]+=num[j];
}
}b^=;
}int ans=;
for(i=;i<=sct;i++){
for(j=;j<=sct;j++) ans=max(ans,f[b^][i][j]);
}printf("%d\n",ans);
}
return ;
}
上一篇:POJ 1038 Bugs Integrated, Inc.


下一篇:POJ 1038 Bugs Integrated Inc (复杂的状压DP)