题意
有一个n*n矩阵aij。n为奇数,m=(n+1)/2。我们每次可以选中一个m*m的子矩阵,将其中所有元素乘以-1.求最后矩阵中所有元素的最大和。n<=33.
分析
这道题是个结论题。
对于第i行的三个值:j、m、m+j,每个子矩阵要么覆盖其中的0个要么覆盖其中2个。
例如:n=5,m=3,那么对于某行的第1、3、4这三个元素,子矩阵要么覆盖其中0个要么覆盖其中2个。对于2、3、5也是如此。
显然对于列也有类似结论。
如果我们把正反视作01(一开始均为0,乘以-1就异或1),设(i,j)的翻转状态为setup[i][j],那么setup[i][j]^setup[i][m]^setup[i][m+j]=0.当然这里要求k
而且,只要setup矩阵满足这一条件,就一定能用一系列操作变换出来这个setup矩阵。
证法其实挺巧的:将每个a[i][j]都视作一维,那么每个m*m的子矩阵都可以视作n*n维线性空间中的向量。所有这些向量都是线性无关的(直观上看,不可能用若干个子矩阵操作将某一个别的子矩阵操作抵消掉)。而一共有m*m种不同的操作,因此最终一定有2^(m*m)个不同的setup矩阵。另一方面,只要确定了左上角的m*m个数,那整个setup矩阵亦随之确定,总数也是2^(m*m)种。所以每个满足条件的setup矩阵一定能变换出来。
因此我们可以O(2^m)枚举setup矩阵第m列的前m个数。确定它们之后,第m列的后n-m个数亦随之确定。然后可以发现,对于j
总复杂度O(m*2^m)。
代码
#include#include #include #include using namespace std; const int INF=0x7fffffff/2; const int SIZEN=50; int N,M; int A[SIZEN][SIZEN]; int setup[SIZEN][SIZEN]; int sgn(int a){//0是未翻,1是翻了 return !a?1:-1; } int single_val(int x,int y){ return sgn(setup[x][y])*A[x][y]; } int calc_unit(int x,int y,int d){//(x,y)的四元组,要求中线均已放在setup中 int ans=0; setup[x][y]=d; ans+=single_val(x,y); setup[x][y+M]=setup[x][y]^setup[x][M]; ans+=single_val(x,y+M); setup[x+M][y]=setup[x][y]^setup[M][y]; ans+=single_val(x+M,y); setup[x+M][y+M]=setup[x+M][y]^setup[x+M][M]; ans+=single_val(x+M,y+M); return ans; } int calc_unit(int x,int y){//(x,y)的四元组的最大值 return max(calc_unit(x,y,0),calc_unit(x,y,1)); } int calc_left(int k,int d){//钦点第M行k列的值为d setup[M][k]=d; setup[M][k+M]=d^setup[M][M]; int ans=0; ans+=single_val(M,k)+single_val(M,k+M); for(int i=1;i >(i-1))&1); } ans=max(ans,calc_all()); } printf("%d\n",ans); } void read(void){ scanf("%d",&N); M=(N+1)/2; for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ scanf("%d",&A[i][j]); } } } int main(){ //freopen("t1.in","r",stdin); read(); work(); return 0; }