Mirror【省选模拟赛】

yanQval毒瘤题

Posted by yjjr's blog on March 27, 2018

标签:状压DP

题目

这里写图片描述

分析

结论:当最优情况下,每行每列镜子的个数都为偶数

题目可以转化为摆放镜子,使得格子中产生的光环最长

所以不需要考虑镜子到底放什么方向

于是我们直接状压一列镜子当前的奇偶性进行转移

时间复杂度

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
#define inf 1e9
const int maxn=(1<<10)+6;
char st[26][26];
int n,m,h[maxn],cnt[maxn],f[maxn][200],g[maxn][200],ans[maxn];
int main()
{
	freopen("mirror.in","r",stdin);
	freopen("mirror.out","w",stdout);
	n=read(),m=read();
	rep(i,1,n)scanf("%s",st[i]+1);
	rep(sta,0,(1<<n)-1){
		int t=0,x=-1;
		rep(i,0,n-1)
			if((sta>>i)&1){
				t+=x*i;
				x*=-1;
			}
		if(x==1)h[sta]=-inf;else h[sta]=t;
	}
	rep(sta,0,(1<<n)-1)cnt[sta]=cnt[sta>>1]+(sta&1);
	rep(sta,0,(1<<n))rep(i,0,n*m)f[sta][i]=-inf;
	f[0][0]=0;
	rep(j,1,m){
		memcpy(g,f,sizeof f);
		rep(sta,0,(1<<n))rep(i,0,n*m)f[sta][i]=-inf;
		int tmp=0;
		rep(i,1,n)if(st[i][j]=='1')tmp^=1<<i-1;
		rep(sta,0,(1<<n))
			rep(i,0,n*m)
				if(g[sta][i]>-inf){
					for(int s=tmp;;s=(s-1)&tmp){
						int t=g[sta][i]+h[s],nm=cnt[s],nm2=cnt[s&sta];
						t+=j*(nm2+nm2-nm);
						f[sta^s][i+nm]=max(f[sta^s][i+nm],t);
						if(!s)break;
					}
				}
	}
	rep(i,0,n*m)ans[i]=f[0][i];
	rep(i,1,n*m)ans[i]=max(ans[i],ans[i-1]);
	rep(i,0,n*m)printf("%d ",4*n*m-2*ans[i]);printf("\n");
    return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr