zoj3158

对于每一行 ，都要从某一位置分成两段 ，由于不能切出0长度的一段，所 以有n - 1个选择 ，一共m行 ，就是(n - 1)m种方案 。由于问题的规模很 小 ，暴力枚举所有情况取最优解就可以了。直接用dfs即可。

#include <iostream>
#include <cstdlib>
#include <string>
#include <cctype>
using namespace std;
const int MAXSIZE = 8;
long nutrition[MAXSIZE][MAXSIZE];
int m, n;
long mindiff = -1;
void dfs(int i, int j, long sumleft, long sumright){
  if(i == m){
      int sum = 0;
    if(sumleft - sumright > 0){
      sum = sumleft - sumright ;
    }else{
        sum = sumright - sumleft;
    }
    if(sum < mindiff || mindiff     == -1){
        mindiff = sum;
    }
    //cout << "left: " << sumleft << endl;
//    cout << "right: " << sumright << endl;
    return ;
  }
 
  for(int k = 1; k < n; k++){
       long tleft = 0;
       long tright = 0;
       for(int s = 0; s < k; s++)
         tleft += nutrition[i][s];
       for(int s = k; s < n; s++)
         tright += nutrition[i][s];
       dfs(i + 1, k, sumleft + tleft, sumright + tright);
  }
}
int main(){
  while(cin >> m >> n){
     for(int i = 0; i < m; i++){
         for(int j = 0; j < n; j++){
           cin >> nutrition[i][j];
        }
     }
     int t;
     cin >> t;
     mindiff = -1;
     for(int i = 1; i < n; i++){
       long sumleft = 0;
       long sumright = 0;
       for(int j = 0; j < i; j++)
         sumleft += nutrition[0][j];
       for(int j = i; j < n; j++)
         sumright += nutrition[0][j];
       dfs(1, i, sumleft, sumright);
     }
     if(mindiff <= t && n != 1 && mindiff != -1)
        cout << mindiff << endl;
     else
        cout << "You'd better buy another one!" << endl;
  }
}