落書きの魔女 (AOJ2314)
苦行だった・・・
問題:
H*Wのマス目がある.それぞれを#か.で塗る いくつかは既にどれで塗るか決まっている.残りのマスの塗り方のうちもっとも#が多いもののマス目全体の#の数を答えよ.正しいかの条件を満たして塗る必要がある".は連結(4-neighborsで)しない","#が(4-neighborsで)木になっている"
H,W<=11.
解答:
面倒なことで有名な,連結状況を持ったbitDPをするだけ.
横一列W個の塗り方はフィボナッチ数233になり,接続関係は高々6個しか連結成分が現れないことを考えるとベル数の0~6項目までの和279くらいで抑えられる.頑張って先に塗り方や接続関係を列挙しとくと,前処理でnxt[i][j][k]=連結状況i,bitがjの時に次の行にbit kをおくと連結状況はどうなるか を超頑張れば求められる.あとはDP.
超頑張れば,というのが厄介で,連結状況って持ちにくくて(例えばvector
で、もっと頭いい方法があって,一マスずつ埋めます.よくあるやつですね.蟻本にも載ってるし,完全に頭悪いやつだ.この方法に関しては公式スライドにのってる.
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef vector<int> vi; typedef vector<vi> vv; typedef pair<int,int> P; vi con[279]; //sum of 0~6th Bell number map<vi,int> inv; //inv of con int mx_[279]; int bits[234]; //11th Fibonacci number vector<P> bitcon[234]; //11010 -> {(0,2),(3,4)} short int nxt[279][234][234]; int C; //con int B; //bits int H,W; string s[11]; int dp[12][279][234]; vi tmp; void dfs(int x,int mx){ con[C]=tmp; mx_[C]=mx; inv[tmp]=C++; // printf("c=%d: ",C-1); // for(int a:tmp) cout<<a<<" "; // puts(""); if(x==6) return; rep(i,mx+1){ tmp.pb(i); dfs(x+1,max(mx,i+1)); tmp.pop_back(); } } inline int cntbit(int x){ if(x==0) return 0; return __builtin_popcount(x); } int par[12]; void init(int N){rep(i,N) par[i]=i;} int find(int x){ if(par[x]==x) return x; return par[x]=find(par[x]); } bool same(int x,int y){ return find(x)==find(y); } void unite(int x,int y){ x=find(x),y=find(y); if(x<y) swap(x,y); par[x]=y; } inline bool _b(int x,int y){ return ((x>>y)&1)==1; } bool is(P x,P y){ return x.fs<y.sc&&y.fs<x.sc; } int main(){ dfs(0,0); cin>>H>>W; rep(i,H) cin>>s[i]; if(W==1){ if(H==1){ if(s[0][0]=='.') puts("0"); else puts("1"); return 0; } rep1(i,H-1) s[0]+=s[i][0]; swap(H,W); } rep(i,1<<W){ bool ok=1; rep(j,W-1) if( !_b(i,j) && !_b(i,j+1) ) ok=0; if(ok||i==0){ bits[B]=i; // printf("bits[%d]=%d\n",B,i); int p=-1; vector<P> vp; rep(j,W+1){ if(_b(i,j)){ if(p<0) p=j; }else{ if(p>=0){ vp.pb(P(p,j)); p=-1; } } } bitcon[B++]=vp; // show(vp.size()); } } // show(B); rep(i,C) rep(j,B) rep(k,B) nxt[i][j][k]=-1; rep(i,C){ vi& vc=con[i]; int sz=vc.size(); rep(j,B){ int& b=bits[j]; vector<P>& bc=bitcon[j]; if(bc.size()!=sz) continue; rep(k,B){ int& nb=bits[k]; vector<P>& nbc=bitcon[k]; int nsz=nbc.size(); if((b|nb)!=(1<<W)-1 && j>0) continue; bool ok=1; rep(d,W-1) if(_b(b,d)&&_b(b,d+1)&&_b(nb,d)&&_b(nb,d+1)) ok=0; if(j>0&&!ok) continue; // if(i==4&&j==6&&k==10) puts("---!!---"); // if(i==4&&j==6&&k==10) show(sz); // if(i==4&&j==6&&k==10) show(nsz); init(sz+nsz); rep(d,sz) rep(e,sz){ if(vc[d]==vc[e]){ unite(d+nsz,e+nsz); // if(i==4&&j==6&&k==10) printf("%d-%d\n",d+nsz,e+nsz); } } bool used[6]={}; rep(d,sz) rep(e,nsz){ if(is(bc[d],nbc[e])){ if(same(d+nsz,e)){ ok=0; goto done; } unite(d+nsz,e); // if(i==4&&j==6&&k==10) printf("%d-%d\n",d+nsz,e); used[vc[d]]=1; } } done: if(ok){ // printf("'nxt[%d][%d][%d]=ok\n",i,j,k); rep(d,mx_[i]) if(!used[d]) ok=0; if(!ok) continue; vi nvc; map<int,int> mp; int Z=0; rep(d,nsz) if(mp.count(find(d))==0) mp[find(d)]=Z++; rep(d,nsz) nvc.pb(mp[find(d)]); if(inv.count(nvc)==0){ show(nsz); for(int a:nvc) cout<<a<<" "; assert(false); } nxt[i][j][k]=inv[nvc]; // printf("nxt[%d][%d][%d]=%d\n",i,j,k,nxt[i][j][k]); // for(int a:nvc) cout<<a<<" "; // puts(""); } } } } if(W==1) nxt[1][1][0]=0; rep(i,H+1) rep(j,C) rep(k,B) dp[i][j][k]=-1; dp[0][0][0]=0; rep(i,H){ bool canuse[234]={}; rep(k,B){ bool ok=1; rep(x,W){ if(s[i][x]=='#'&&!_b(bits[k],x) ) ok=0; if(s[i][x]=='.'&& _b(bits[k],x) ) ok=0; } canuse[k]=ok; // if(ok) printf("canuse[%d]=%d\n",k,ok); } rep(j,C) rep(k,B){ if(dp[i][j][k]<0) continue; // printf("i,j,k=(%d,%d,%d)\n",i,j,k); if(i>0&&k==0&&W>1) continue; rep(l,B){ if(!canuse[l]) continue; if(W>1&&l==0) continue; // printf(" i,j,k=(%d,%d,%d)\n",i,j,k); // show(l); // show(nxt[j][k][l]); if(nxt[j][k][l]>=0){ chmax(dp[i+1][nxt[j][k][l]][l],dp[i][j][k]+cntbit(bits[l])); // printf("dp[%d][%d][%d],dp[%d][%d][%d]+%d\n",i+1,nxt[j][k][l],l,i,j,k,cntbit(bits[l])); } } } } int ans=-1; rep(j,C){ bool ok=1; rep(k,con[j].size()) if(con[j][k]>0) ok=0; if(!ok) continue; // show(j); rep(k,B){ chmax(ans,dp[H][j][k]); // printf("dp[%d][%d][%d]=%d\n",H,j,k,dp[H][j][k]); } } cout<<ans<<endl; }
闇