题目描述：


现在有一块长条形的土地，这个土地我们可以看成是由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。若有多解输出最靠左的划分。


输入例子:

[[1,1,1,1],[0,0,0,0],[1,0,1,1]],4,3


输出例子:

[0,1]


方法声明：

vector<int>getPartition(constvector<vector<int>>&land,intn,intm){//writecodehere}



分析：

根据题目要求，我们需要找到一个边界，这个边界的左边都为 0 ，右边都为 1 ，而且，这个划分必须与专家评估的结果不同的土地（也就是方格）数最少，


如下示例：

输入：

[[1,1,1,1],[0,0,0,0],[1,0,1,1]],4,3

也就是 4 块土地，3次评估

则所有的情况如下图：


将每种情况对应的专家评估不吻合的土地数加起来：

遇到不吻合的土地数相同的情况下（如上面 1111 和 0011），取最左的划分，也就是 1111，则划分为 0,1


再举一个例子：

所有情况如下：

所以划分就为： 1 , 2


根据上述思想，写代码就容易多了：


vector<int>getPartition(constvector<vector<int>>&land,intn,intm){int*a=newint[n];for(inti=0;i<n;++i)//全部置1，从全1的情况开始{a[i]=1;}intleft=0;//划分的左边界intright=1;//计划分的右边界intmindif=n*m;//最少的不吻合的土地数intdifCount=0;//用来记录不吻合的个数intzeroCount=0;//划分序列中0的个数intdif=0;//每种情况的不吻合的土地数for(intindex=0;index<n+1;++index)//一共有n+1种可能组合{for(inti=0;i<m;++i){for(intj=0;j<n;++j){if(land[i][j]!=a[j])++difCount;}dif+=difCount;difCount=0;}if(dif<=mindif){if(dif<mindif){mindif=dif;left=zeroCount;right=zeroCount+1;}elseif(zeroCount<left){left=zeroCount;right=zeroCount+1;}}dif=0;if(zeroCount<n)a[zeroCount++]=0;}delete[]a;a=NULL;vector<int>ret;ret.push_back(left);ret.push_back(right);returnret;}