标签：状压DP
题目
分析
结论：当最优情况下，每行每列镜子的个数都为偶数
题目可以转化为摆放镜子，使得格子中产生的光环最长
所以不需要考虑镜子到底放什么方向
于是我们直接状压一列镜子当前的奇偶性进行转移
时间复杂度\(O(4^n*n*m^2)\)
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;
}
