题解 | #分田地#

using System;
using System.Collections;
using System.Collections.Generic;
public class Program {

    public static int[,] field;//每块地的价值
    public static int[,] sum;//从0，0到某一点的矩形地的总价值
    public static void Main() {
        string line;
        while ((line = System.Console.ReadLine ()) !=
                null) { // 注意 while 处理多个 case
            string[] tokens = line.Split(' ');
            int n = int.Parse(tokens[0]);
            int m = int.Parse(tokens[1]);
            field = new int[n, m];
            sum = new int[n + 1, m + 1];
            for (int i = 0; i < n; i++) {
                line = Console.ReadLine();
                for (int j = 0; j < m; j++) {
                    field[i, j] = line[j] - '0';
                }
            }
            //给sum赋值
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    int temp = 0;
                    for (int k = 0; k < i; k++) {
                        for (int l = 0; l < j; l++) {
                            temp += field[k, l];
                        }
                    }
                    sum[i, j] = temp;
                }
            }
            //穷举竖向3刀，划分横向3刀时，符合条件则划一刀，用count计算符合条件的行，count==4则代表每块位置的价值都大于min
            int left = 0;
            int right = sum[n,m] / 16 + 1;
            int ans = 0;
            while(left <= right){
                int min = (left + right) / 2;
                bool flag = false;
                for(int i = 1; i <= m - 3; i++){//i是第一刀的位置
                    for(int j = i + 1; j <= m - 2; j++){//j是第二刀的位置
                        for(int k = j + 1; k <= m - 1; k++){//k是第三刀的位置
                            //对于这种割法，依次判断是否可以割出最小价值>=min的三刀横向刀
                            int lastcut = 0;
                            int count = 0;
                            for(int l = 1; l <= n; l++){
                                bool s1 = judge(lastcut,0,l,i,min);
                                bool s2 = judge(lastcut,i,l,j,min);
                                bool s3 = judge(lastcut,j,l,k,min);
                                bool s4 = judge(lastcut,k,l,m,min);
                                if(s1 && s2 && s3 && s4){
                                    lastcut = l;
                                    count++;
                                }
                            }
                            if(count >= 4) {
                                flag = true;
                                break;
                            }
                        }
                        if(flag) break;
                    }
                    if(flag) break;
                }
                if(flag){
                    ans = min;
                    left = min + 1;
                }else{
                    right = min - 1;
                }
            }
            Console.WriteLine(ans);
        }
    }
    //判断两个顶点之间的田地的价值是否大于num
    public static bool judge(int x1, int y1, int x2, int y2, int num){
        int _temp = sum[x2,y2] - sum[x2,y1] - sum[x1,y2] + sum[x1,y1];
        if(Math.Abs(_temp) >= num) return true;
        else return false;
    }
}

C#需要把时间抠的好死，用二分查找，还有一个细节，16块田地中，最小的田地最大化，这块地一定不能大于田地总价值/16，所以可以把二分查找的右指针设置成sum[n,m]/16 +1开始；