题解 CF321D 【Ciel and Flipboard】
xzyxzy
2018-06-24 16:53:21
## orz wfj_2048
Tag:我也不知道叫什么,叫思维题吧。。
# Step1 性质
设$rev[i][j]$表示$(i,j)$这个点最终状态$(0/1)$是否取反
那么有$rev[i][k]\ xor \ rev[i][m]\ xor \ rev[i][m+k]=0$
因为第i行这三个点要么被翻到2个要么0个
同理列也有这个性质
# Step2 推导
那么我们枚举左上的一个四分之一矩形就可以对称出所有位置了
同时会发现,在$(1..m-1,1..m-1)$这四分之一个矩形内的点的$rev$线性无关,也就是说相互独立互不影响,可以同时取最优情况
当$(x,y)(x<m,y<m)$取某种情况时,它对称的三个点的情况取决于$(x,m),(m,y)$的决策,那么我们从枚举一个矩形降到了枚举两条线段
继续优化
如果只枚举$(1...m-1,m)$呢,可以发现$(m,k),k<m$的决策只影响到$(1..m-1,k)$的对称情况,所以$(m,1..m-1)$这些点的决策又是相互独立的,同时可以取到最优决策
由此,只需要枚举$(1...m-1,m)$的决策,然后分别嵌套取最优方案即可
~~代码极好理解~~
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int r[40][40],v[40][40],n,m,ans=-1e9;
int F(int x,int y){return r[x][y]?-v[x][y]:v[x][y];}
int query(int x,int y,int d)
{
r[x][y]=d; r[x+m][y]=r[m][y]^d;
r[x][y+m]=r[x][m]^d;
r[x+m][y+m]=r[m][y+m]^r[x][y+m];
return F(x,y)+F(x+m,y)+F(x,y+m)+F(x+m,y+m);
}
int query(int y,int d)
{
int res=0; r[m][y]=d; r[m][y+m]=r[m][m]^d;
res+=F(m,y)+F(m,y+m);
for(int x=1;x<m;x++) res+=max(query(x,y,0),query(x,y,1));
return res;
}
int Calc()
{
int res=0; for(int x=1;x<=n;x++) res+=F(x,m);
for(int y=1;y<m;y++) res+=max(query(y,0),query(y,1));
return res;
}
int main()
{
scanf("%d",&n); m=(n+1)>>1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&v[i][j]);
for(int zt=0;zt<(1<<m);zt++)
{
for(int x=1;x<=m;x++) r[x][m]=zt>>(x-1)&1;
for(int x=1;x<m;x++) r[x+m][m]=r[m][m]^r[x][m];
ans=max(ans,Calc());
}
printf("%d\n",ans);
}
```
~~虽然和本题完全没有关系但是还是打个广告~~「[blog](https://www.cnblogs.com/xzyxzy/)」