现在有一块长方形土地，可看成由n个小方块组成，这n个小方块我们依次编号为1到n。现要在这块土地划分成两大块，分别种上不同的作物A和B，划分必须在某两个小方块之间进行，或者在土地的最左端或最右端，若划分在第i块和第i+1块之间，则划分后第1至第i块地种A，剩下的种B。现有一些专家对土地进行了检测，他们每个人评估了每块土地适合种的作物。

请你找到一个合适的划分，使得其余所有专家的评估最吻合，也就是说，你划分到A而专家评估为B的次数和你划分到B而专家评估为A的次数之和最小。

输入描述：

每组数据 给定一个专家评估表land(其中0为评估A，1为评估B)，已及小块数量n（1<=n<=300）,专家评估次数为m（1<=m<=300）

输出描述：

请返回你的划分，即i和i+1.若在最左端，则输出0,1；在最右端则输出n,n+1；。若有多解输出最靠左的划分。

例如：

//有4个小方块，专家鉴定了3次

输入{

{1，1，1，1}，{0，0，0，0}，{1，0，1，1}}，4，3

输出{0，1}

代码实现：

Land.h

#pragma once#include 
     
      #include 
      
       #include 
       
        using namespace std;class Partition {public:	 vector
        
          getPartition(const vector
         
          
            >& land, int n, int m)   { int count = pow(2, n) - 1;//可能划分的情况共有count种 int i = 0, j = 0; int dstres = n*m; int lessCount = 0; while (count >= 0){ EffectiveCount(&count,n); int res = 0; while (i
           
            0 && ((count & 0x01) == bit)) { count = count >> 1; ret++; } vector
            
              a = { n-ret,n-ret+1 }; return a; }private: void EffectiveCount(int* count,int n)//跳过无效的count    比如1100有效    1011和1010无效 { int flag = 0; int k = 1; int tmp = *count; while (*count > 1){ int ret = (tmp >> 0) & 0x01; while (k < n){ if (ret != ((tmp >> k) & 0x01)){ flag++; if (flag == 2){ (*count)--; break; } ret = (tmp >> k) & 0x01; } k++; } if (flag != 2) break; k = 1; } }};
            
           
          
         
        
       
      
     

Test.cpp

#include"Land.h"using namespace std;void Test(){	Partition a;	int n = 4;	int m = 3;	//int n = 3;	//int m = 4;	vector
     
      
        > land = { { 1, 1, 1, 1 }, { 0, 0, 0, 0, }, {1, 0, 1, 1} };	//vector
       
        
          > land = { { 1, 1, 0 }, { 0, 0, 0 }, { 1, 0, 1 }, {1, 0, 0} };	vector
         
           array = a.getPartition(land, n, m);	printf("{%d,%d}\n", array[0], array[1]);}int main(){	Test();	system("pause");	return 0;}
         
        
       
      
     

运行结果：

输入为

 { { 1, 1, 1, 1 }, { 0, 0, 0, 0, }, {1, 0, 1, 1} }  n=4  m=3

输出为

 

====================================================================

输入为

  { { 1, 1, 0 }, { 0, 0, 0 }, { 1, 0, 1 }, {1, 0, 0} }   n=3  m=4

输出为