2532023_ac_0ms_504k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include  <iostream> 
#include  <cstdlib> 
#include  <cmath> 
 using   namespace  std;
int min(int a,int b)
{return a<b?a:b;}
 const   int  INF  =   2000000000 ;
 int  f[ 9 ][ 9 ][ 9 ][ 9 ][ 15 ];
 int  s[ 9 ][ 9 ][ 9 ][ 9 ];
 int  d[ 9 ][ 9 ];

 void  init()
  {
     int  x1, y1, x2, y2;
     int  i, j;
     int  sum;
     for  (x1 = 1 ; x1 <= 8 ; x1 ++ )
         for  (y1 = 1 ; y1 <= 8 ; y1 ++ )
             for  (x2 = x1; x2 <= 8 ; x2 ++ )
                 for  (y2 = y1; y2 <= 8 ; y2 ++ )
                  {
                    sum  =   0 ;
                     for  (i = x1; i <= x2; i ++ )
                         for  (j = y1; j <= y2; j ++ )
                            sum  +=  d[i][j];
                    s[x1][y1][x2][y2]  =  sum;
                    f[x1][y1][x2][y2][ 1 ]  =  sum  *  sum;
                } 
} 
 int  main()
  {

     int  n;
     int  i, j, k;
     int  x1, y1, x2, y2;
     int  a, b;
     int  t, tmp;
     double  p  =   0 ;

    scanf( "%d" ,  & n);
    
     for  (i = 1 ; i <= 8 ; i ++ )
         for  (j = 1 ; j <= 8 ; j ++ )
          {
            scanf( "%d" ,  & d[i][j]);
            p  +=  d[i][j];
        } 
 
    p  /=  n;

 
    init();

     for  (k = 2 ; k <= n; k ++ )
      {
         for  (x1 = 1 ; x1 <= 8 ; x1 ++ )
             for  (y1 = 1 ; y1 <= 8 ; y1 ++ )
                 for  (x2 = x1; x2 <= 8 ; x2 ++ )
                     for  (y2 = y1; y2 <= 8 ; y2 ++ )
                      {
                        tmp  =  INF;

                          for  (a = x1; a < x2; a ++ )
                          {
                            t  =  min(f[x1][y1][a][y2][k - 1 ] + s[a + 1 ][y1][x2][y2] * s[a + 1 ][y1][x2][y2]
                                , f[a + 1 ][y1][x2][y2][k - 1 ] + s[x1][y1][a][y2] * s[x1][y1][a][y2]);
                             if  (tmp  >  t) 
                                tmp  =  t;
                        } 

                          for  (b = y1; b < y2; b ++ )
                          {
                            t  =  min(f[x1][y1][x2][b][k - 1 ] + s[x1][b + 1 ][x2][y2] * s[x1][b + 1 ][x2][y2]
                                , f[x1][b + 1 ][x2][y2][k - 1 ] + s[x1][y1][x2][b] * s[x1][y1][x2][b]);
                             if  (tmp  >  t)
                                tmp  =  t;
                        } 
                        
                        f[x1][y1][x2][y2][k]  =  tmp;
                    } 
    } 
    printf( "%.3f\n" , sqrt( double (f[ 1 ][ 1 ][ 8 ][ 8 ][n]) / double (n) - p * p));
     return   0 ;
}