题解 CF321D 【Ciel and Flipboard】

## 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/)」