题解 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)的决策，然后分别嵌套取最优方案即可

代码极好理解

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