题意：给出一个1000*1000的方阵，问你任意“十字乘积”的最大值。十字可以是对角线的，四边长度要相等。
题解：用8个数组维护8个方向的乘积，枚举任意一个点。（乘积最大相应的取对数也是最大的，将n项乘积转换成前n项和）。
#include<bits/stdc++.h> using namespace std; #define N 2010 int d[N][N]; double s[8][N][N]; int p[8][N][N]; typedef long long LL; #define MOD 1000000007 //0,1 ,1,1, 1,0, 1,-1, 0,-1, -1,-1, -1,0, -1,1 int dre[]={0,1 ,1,1, 1,0, 1,-1, 0,-1, -1,-1, -1,0, -1,1}; double lg[4]; inline bool check(int x,int y,int n,int m){ return x>=1&&x<=n&&y<=m&&y>=1; } void dfs(int x,int y,int k,int n,int m){ int pr = dre[k*2],pc = dre[k*2+1]; int tx = x+pr,ty=y+pc; if(check(tx,ty,n,m)){ if(d[tx][ty]==0){ s[k][tx][ty]=0; p[k][tx][ty]=0; }else{ s[k][tx][ty]=s[k][x][y]+lg[d[tx][ty]]; // if(k==3){ // printf("%d,%d(%.2lf)--->%d,%d(%.2lf,%d,%.2lf)\n",x,y,s[k][x][y],tx,ty,s[k][tx][ty],d[tx][ty],lg[d[tx][ty]]); // } p[k][tx][ty]=p[k][x][y]+1; } dfs(tx,ty,k,n,m); } } int main(){ int n; lg[1]=0,lg[2]=log(2.),lg[3]=log(3.); //lg[1]=1,lg[2]=2,lg[3]=3; while(scanf(" %d",&n)==1){ //vector<vector<int> > d(n+2,vector<int>(n+2,0)); for(int i=0;i<=n+1;i++){ for(int j=0;j<=n+1;j++){ d[i][j]=0; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf(" %1d",&d[i][j]); } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // printf("%d ",d[i][j]); // } // puts("");fflush(stdout); // } for(int k=0;k<8;k++){ for(int i=0;i<=n+1;i++){ p[k][i][0]=0; s[k][i][0]=0; dfs(i,0,k,n,n); p[k][i][n+1]=0; s[k][i][n+1]=0; dfs(i,n+1,k,n,n); } for(int j=0;j<=n+1;j++){ p[k][0][j]=0; s[k][0][j]=0; dfs(0,j,k,n,n); p[k][n+1][j]=0; s[k][n+1][j]=0; dfs(n+1,j,k,n,n); } } // for(int k=0;k<8;k++){ // printf("K:%d\n",k); // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // printf("%.2lf(%d) ",s[k][i][j],p[k][i][j]); // } // puts("");fflush(stdout); // } // } double ms = -1; int rx,ry,t=-1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(d[i][j]==0) continue; int dm = p[0][i][j]; for(int k=0;k<=6;k+=2){ dm = min(dm,p[k][i][j]); } //printf("%d %d(t1)(%d)\n",i,j,dm); double ts = 0; for(int k=0;k<=6;k+=2){ ts += s[k][i][j]-s[k][i-(dre[k*2]*dm)][j-dre[2*k+1]*dm]; } ts -= lg[d[i][j]] * 3; if(ts>ms){ ms = ts; t = 1; rx = i; ry = j; } dm = p[1][i][j]; for(int k=3;k<=7;k+=2){ dm = min(dm,p[k][i][j]); } //printf("%d %d(t2)(%d)\n",i,j,dm); ts = 0; for(int k=1;k<=7;k+=2){ ts += s[k][i][j] - s[k][i-(dre[k*2]*dm)][j-dre[2*k+1]*dm]; } ts -= lg[d[i][j]] * 3; if(ts>ms){ ms = ts; t = 2; rx = i; ry = j; } } } //printf("%d %d %d\n",rx,ry,t); if(t==-1){ printf("0\n"); continue; } LL ret = 1; if(t==1){ int dm = p[0][rx][ry]; for(int k=0;k<=6;k+=2){ dm = min(dm,p[k][rx][ry]); } ret = d[rx][ry]; for(int k=0;k<=6;k+=2){ for(int j = 1;j<dm;j++){ ret = ret*d[rx-dre[k*2]*j][ry-dre[2*k+1]*j]%MOD; } } }else{ int dm = p[1][rx][ry]; for(int k=1;k<=7;k+=2){ dm = min(dm,p[k][rx][ry]); } //printf("%d %d %d\n",rx,ry,dm); ret = d[rx][ry]; for(int k=1;k<=7;k+=2){ for(int j = 1;j<dm;j++){ ret = ret*d[rx-dre[k*2]*j][ry-dre[2*k+1]*j]%MOD; } } } printf("%I64d\n",ret); //fflush(stdout); } return 0; } /* 4 1233 0213 2020 0303 */
