OpenJudge/Poj 1191 棋盘分割

1.链接地址：

http://bailian.openjudge.cn/practice/1191/

http://poj.org/problem?id=1191

2.题目：

3.思路：

确定公式的常量

深搜+剪枝

4.代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #define NUM 8

 using namespace std;

 double res_sigma;

 int n;

 int arr[NUM][NUM];

 double all_avg;

 double sigma;

 void dfs(int x1,int y1,int x2,int y2,int sum,int cut)

 {

     int k,i,j;

     int temp_sum,temp_avg;

     double temp;

     if(cut == )

     {

         temp = (sum - all_avg) * (sum - all_avg);

         if(sigma + temp < res_sigma) {res_sigma = sigma + temp;}

         return;

     }

     temp_sum = ;

     for(k = y1; k < y2; ++k)

     {

         for(j = x1; j <= x2; ++j) temp_sum += arr[k][j];

         temp_avg = temp_sum;

         temp = (all_avg - temp_avg) * (all_avg - temp_avg);

         if(sigma + temp < res_sigma)

         {

             sigma += temp;

             dfs(x1,k + ,x2,y2,sum - temp_sum,cut - );

             sigma -= temp;

         }

         temp_avg = sum - temp_sum;

         temp = (all_avg - temp_avg) * (all_avg - temp_avg);

         if(sigma + temp < res_sigma)

         {

             sigma += temp;

             dfs(x1,y1,x2,k,temp_sum,cut - );

             sigma -= temp;

         }

     }

     temp_sum = ;

     for(k = x1; k < x2; ++k)

     {

         for(i = y1; i <= y2; ++i) temp_sum += arr[i][k];

         temp_avg = temp_sum;

         temp = (all_avg - temp_avg) * (all_avg - temp_avg);

         if(sigma + temp < res_sigma)

         {

             sigma += temp;

             dfs(k + ,y1,x2,y2,sum - temp_sum,cut - );

             sigma -= temp;

         }

         temp_avg = sum - temp_sum;

         temp = (temp_avg - all_avg) * (temp_avg - all_avg);

         if(sigma + temp < res_sigma)

         {

             sigma += temp;

             dfs(x1,y1,k,y2,temp_sum,cut - );

             sigma -= temp;

         }

     }

 }

 int main()

 {

     //freopen("C://input.txt","r",stdin);

     cin >> n;

     int i,j;

     int sum = ;

     for(i = ; i < NUM; ++i)

     {

         for(j = ; j < NUM; ++j)

         {

             cin >> arr[i][j];

             sum += arr[i][j];

         }

     }

     all_avg = sum * 1.0 / n;

     res_sigma = sum * sum * n;

     dfs(,,NUM - ,NUM - ,sum,n - );

     cout.setf(ios::fixed);

     cout.precision();

     cout << sqrt(res_sigma / n) << endl;

     return ;

 }