2020夏季牛客多校訓練キャンプ第8場(C)Cinema(状圧DP、離散化)

Cinema
原題はこちらをご覧ください
タイトルの説明:
中国の映画館は閉鎖6ヶ月後に再開され、コロナウイルスの伝播を遅らせるのを助ける.アポロの映画館はn n n席があり、各列にm m席行があります.x番目のx行とy番目のy列の座席を一対の数字(x,y)(x,y)(x,y)として表す.この政策によると、映画館の人々は社交的な距離を保つ必要がある.そのため、二人は隣の二つの席に座ることができません.両席(x 1,y 1)(x 2,y 2)(x_1,y_1)(x_2,y_2)(x 1,y 1)(x 2,y 2)(x 2,y 2)(x 2,y 2)が同じエッジを持っている場合は,隣接していると考えられる,すなわち,∣x 1−x 2∣＋∣y 1−y 2∣＝1｜x_1-x_2 | + | y_1-y_2|=1∣x 1−x 2∣+∣y 1−y 2∣=1人々は興行収入に来て1枚1枚切符を買って、自分で席を選ぶことを許可します.人々はどんな有効な席を選ぶことができます.他の人が選択し、他の人と隣接しない席でなければ、その席は有効です.有効な席がなければ、映画館のレジはチケットの販売を停止します.映画館のオーナーとして、アポロは最悪の場合に販売できる最低票数を知りたいと思っています.チケットを購入するのに十分な人がいると仮定することができます(つまり、映画館のレジは有効な席がないまでチケットを販売し続けます).
説明を入力:
入力された第1行は、試験例の数T(1≦T≦1000)mathbf{T}(1leqmathbf{T}leq 1000)T(1≦T≦1000)を与える.Tmathbf{T}T群の試験例は以下の通りである.各試験例は、1行に2つの整数n(1≦n≦1000)n(1≦n≦1000)n(1≦n≦1000)とm(1≦m≦15)m(1≦m≦15)m(1≦m≦15)m(1≦m≦15)からなり、それぞれ行数と列数を表す.
出力の説明:
各試験例について、出力行はC a s e Case#x x:y y yを含み、x xは試験例番号(1 1から)であり、y y yは最悪の場合に販売可能な最小票数である.その後、n n n n行を印刷し、各行m文字を印刷し、y y y y枚の映画チケットしか販売できない場合を示す.「*」は座席が選択されたことを示す.座席が選択されていないことを示します.複数の有効な答えがある場合は、いずれかを出力できます.
サンプル入力:

3
3 3
4 5
1 5

サンプル出力:

Case #1: 3
*.*
...
.*.
Case #2: 6
..*.*
*....
...*.
.*..*
Case #3: 2
.*.*.

考え方:
状圧d p dpはmの取値範囲を見ると状圧を思い浮かべます.まず、一般的な状圧を考えてみましょう.0はこの席に人がいないことを示し、1はこの席に人がいないことを示します.しかし、私たちの頭を叩くと、この2つが足りないことがわかります.最も多く求めるなら、2つで十分です.1つの席が4つの席に貢献して座ることができなくて、もし2つの席の貢献が重なったら、それはきっとお得ではありません.だから、私たちはこの席の周りに人がいるかどうかを貯金しなければなりません.そこで、状圧の書き方を再定義します.

0はこの席に人がいないことを示し、周囲の4つの席にも

人がいないことを示している.

1はこの席には誰もいないが、周りの4つの席(必ずしも人がいるとは限らない)には

人がいることを示している.

2はこの席に人がいることを示しています

この時、私たちの任務はすでに大半を完成しました.3進数の状圧です.しかし、データ範囲を見ると、3 15∗1000 3^{15}*1000 315∗1000が直接爆発したことがわかります...ましてや1000 1000組のデータもあります.次に私たちの任務は、データをどのように圧縮するかです.ブラシの問題が広い人がこの問題をしたことがある:四角い数を取ると、この問題の状況は本題と似ていて、データを圧縮する必要があることがわかります.d p dp dp配列に格納されている状態はすべて役に立つのではないでしょうか.明らかにそうではありません.例えば、2つが隣接している場合は、考慮する必要はありません.そのため、離散化という操作が必要です.同じ行には多くの不法な状況があります.

両2隣接

0 0と2隣接

両0隣接

隣接する2つの1であり、周囲に2

はない.
だから私たちはすべてのmの不法な状況を前処理して除去すれば、爆発しません.
A C AC AC C o d e Code Code:

#include
#define ll long long
using namespace std;
struct node{
	int first;
	int second;
	node(){}
	node(int _f,int _s){first=_f,second=_s;}
	bool operator < (const node &n1)const{
		return first<n1.first;
	}
};
const int MAXM=16;
const int MAXX=1005;
const int MAXN=6600;
const int MAX=13e6+5;
int qm[MAXX],sta[MAXN],id[MAX],dp[MAXX][MAXN];
int pre[MAXX][MAXN],num2[MAXN],num0[MAXN],ans[MAXN];
int tot,t,n,m;
vector<node> vec[MAXN];
vector<int> nxt[MAXN],sol[MAXN];
void dfs(int pos,int now,int mm){
	if(pos==mm){
		if(pos>=2&&(now%3==1)&&(now/3%3==1)&&(pos-2<0||now/9%3!=2))return;
		id[now]=tot;sta[tot++]=now;return;
	}if(!pos){
		dfs(pos+1,now*3,mm);
		dfs(pos+1,now*3+1,mm);
		dfs(pos+1,now*3+2,mm);
		return;
	}if(now%3^1){dfs(pos+1,now*3+1,mm);return;}
	dfs(pos+1,now*3+2,mm);
	if(!(pos>=2&&(now%3==1)&&now/3%3==1&&(pos-2<0||now/9%3!=2))){
		dfs(pos+1,now*3,mm);
		dfs(pos+1,now*3+1,mm);
	}
}int get2(int x){
	int ret=0;
	while(x){ret+=(x%3==2);x/=3;}
	return ret;
}int get0(int x,int mm){
	int ret=0;
	for(int i=0;i<mm;++i){ret+=(x%3==0);x/=3;}
	return ret;
}void search(vector<int> &res,int a[],int mm,int now,int pos){
	if(pos>=mm){res.push_back(now);return;}
	if(a[pos]==2) search(res,a,mm,now*3+1,pos+1);
	else if(!a[pos]){
		if(pos+1<mm) search(res,a,mm,(now*3+2)*3+1,pos+2);
		else search(res,a,mm,now*3+2,pos+1);
	}else{
		if(pos+1<mm){
			if(!a[pos+1]) search(res,a,mm,now*3+1,pos+1);
			else if(a[pos+1]==2){
				search(res,a,mm,now*3,pos+1);
				search(res,a,mm,now*3+2,pos+1);
			}else{
				if(pos+2>=mm||a[pos+2]==2){
					search(res,a,mm,(now*3+2)*3+1,pos+2);
					search(res,a,mm,(now*3+1)*3+2,pos+2);
				}else if(!a[pos+2]){
					search(res,a,mm,now*9+1,pos+2);
					search(res,a,mm,(now*3+2)*3+1,pos+2);
				}else if(pos+3>=mm||a[pos+3]==2){
					search(res,a,mm,(now*3+2)*3+1,pos+2);
					search(res,a,mm,(now*9+1)*3+2,pos+3);
					search(res,a,mm,((now*3+1)*3+2)*3+1,pos+3);
				}
			}
			
		}else{
			search(res,a,mm,now*3,pos+1);
			search(res,a,mm,now*3+2,pos+1);
		}
	}
}
bool check(int x,int mm){
	int a[MAXN];
	for(int i=0;i<mm;++i){a[i]=x%3;x/=3;}
	for(int i=0;i<mm;++i)
		if(a[i]==1&&(!i||a[i-1]!=2)&&(i==mm-1||a[i+1]!=2))
			return false;
	return true;
}
int a[MAXN];
void solve(vector<node> query,int mm){
	int qsize=query.size();
	if(!qsize) return;
	sort(query.begin(),query.end());
	tot=0;
	dfs(0,0,mm);
	for(int i=0;i<tot;++i){
		num2[i]=get2(sta[i]);
		num0[i]=get0(sta[i],mm);
		nxt[i].clear();
		int ts=sta[i];
		for(int j=mm-1;j>=0;--j){
			a[j]=ts%3;
			ts/=3;
		}search(nxt[i],a,mm,0,0);
	}memset(dp,-1,sizeof(dp));
	for(int i=0;i<tot;++i)
		if(check(sta[i],mm))
			dp[1][i]=num2[i];
	int qid=0;
	for(int i=1;i<=MAXX-5;++i){
		while(qid<qsize&&query[qid].first==i){
			int qin=query[qid].second;
			ans[qin]=i*mm;
			sol[qin].clear();
			int tmp=-1;
			for(int j=0;j<tot;++j)
				if(dp[i][j]!=-1&&ans[qin]>dp[i][j]+num0[j]){
					tmp=j;
					ans[qin]=dp[i][j]+num0[j];
				}
			sol[qin].push_back(sta[tmp]);
			for(int j=i;j>1;j--){
				tmp=pre[j][tmp];
				sol[qin].push_back(sta[tmp]);
			}qid++;
		}if(qid==qsize) break;
		for(int j=0;j<tot;++j){
			if(dp[i][j]==-1) continue;
			for(int k=0;k<nxt[j].size();++k){
				int v=nxt[j][k];
				int idd=id[v];
				if(dp[i+1][idd]==-1||dp[i+1][idd]>dp[i][j]+num2[idd]){
					dp[i+1][idd]=dp[i][j]+num2[idd];
					pre[i+1][idd]=j;
				}
			}
		}
	}
}void print(vector<int> tor,int mm){
	for(int i=tor.size()-1;i>=0;--i){
		int v=tor[i];
		for(int j=0;j<mm;++j){
			if(v%3==2||(!i&&v%3==0)) printf("*");
			else printf(".");
			v/=3;
		}puts("");
	}
}int main(){
	for(int i=1;i<MAXM;++i)
		vec[i].clear();
	scanf("%d",&t);
	for(int i=0;i<t;++i){
		scanf("%d%d",&n,&m);
		vec[m].push_back(node(n,i));
		qm[i]=m;
	}for(int i=1;i<MAXM;++i)
		solve(vec[i],i);
	for(int Case=0;Case<t;++Case){
		printf("Case #%d: %d
",Case+1,ans[Case]);
		print(sol[Case],qm[Case]);
	}
}