题意: 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=14,maxn=155,maxs=300;
- const int f11=16777215,f01=22369621;
- const int b0101=5,b101010=42,b11=3,b1111=15,b111111=63;
- inline LL rd(){
- LL x=0;char c=getchar();int neg=1;
- while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
- while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
- return x*neg;
- }
- int sta[maxs],fsta[maxs],sct,mp[maxn];
- int f[2][maxs][maxs];
- int N,M,K;char num[maxs];
- inline void print(int x,int y){
- if(y<=M*2-2) print(x>>1,y+1);
- printf("%d",x&1);
- }
- 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+1,s,fs,c);
- if(x<=M-2){
- dfs(x+2,s|(b0101<<(x<<1)),fs|(b1111<<(x<<1)),c+1);
- }if(x<=M-3){
- dfs(x+3,s|(b101010<<(x<<1)),fs|(b111111<<(x<<1)),c+1);
- }
- }
- inline bool judge1(int i,int s){
- return (s&(mp[i]|mp[i+1]))||(s&f01&mp[i+2]);
- }
- 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,0,sizeof(mp));
- sct=0;dfs(0,0,0,0);
- for(i=1;i<=K;i++){
- int a=rd(),b=rd();
- mp[a-1]|=b11<<((b-1)<<1);
- }mp[N+1]=mp[N]=f11;
- bool b=0;
- for(i=0;i<N-1;i++){
- memset(f[b],-1,sizeof(f[b]));
- for(j=1;j<=sct;j++){
- if(judge1(i,sta[j])) continue;
- if(!i){f[b][j][1]=num[j];continue;}
- for(k=1;k<=sct;k++){
- if((sta[j]&fsta[k])||judge1(i-1,sta[k])) continue;
- for(l=1;l<=sct;l++){
- if(fsta[j]&(sta[l]&f01)) continue;
- f[b][j][k]=max(f[b][j][k],f[b^1][k][l]);
- }if(f[b][j][k]==-1) continue;
- f[b][j][k]+=num[j];
- }
- }b^=1;
- }int ans=0;
- for(i=1;i<=sct;i++){
- for(j=1;j<=sct;j++) ans=max(ans,f[b^1][i][j]);
- }printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2722760.html