題目大意
牛牛和 15 個(gè)朋友來(lái)玩打土豪分田地的游戲，牛牛決定讓你來(lái)分田地虱疏，地主的田地可以看成是一個(gè)矩形，每個(gè)位置有一個(gè)價(jià)值榜贴。分割田地的方法是橫豎各切三刀矢赁，分成 16 份糯笙，作為領(lǐng)導(dǎo)干部，牛帕靡總是會(huì)選擇其中總價(jià)值最小的一份田地给涕， 作為牛牛最好的朋友，你希望牛牛取得的田地的價(jià)值和盡可能大额获，你知道這個(gè)值最大可以是多少嗎够庙？
輸入描述:
每個(gè)輸入包含 1 個(gè)測(cè)試用例。每個(gè)測(cè)試用例的第一行包含兩個(gè)整數(shù) n 和 m（1 <= n, m <= 75）抄邀，表示田地的大小耘眨，接下來(lái)的 n 行，每行包含 m 個(gè) 0-9 之間的數(shù)字撤摸，表示每塊位置的價(jià)值毅桃。
輸出描述:
輸出一行表示牛牛所能取得的最大的價(jià)值。
示例1
輸入
4 4
3332
3233
3332
2323
輸出
2
分析
題目的任務(wù)是在一個(gè)矩陣上橫切3刀准夷，豎切3刀钥飞，直接暴力枚舉的話復(fù)雜度是n^6。實(shí)際上題目要求的是使最小值最大衫嵌，故可以二分答案读宙。
常見(jiàn)的方法是二分答案x，先枚舉橫切三刀的位置楔绞，假設(shè)為R1结闸，R2，R3酒朵。接下來(lái)是判斷能否通過(guò)豎切3刀桦锄，使得16塊區(qū)域的和都不小于x。這一部分的代碼如下：
void work()
{
int ans = 0;
for(R1=1;R1<n;R1++)
for(R2=R1+1;R2<n;R2++)
for(R3=R2+1;R3<n;R3++)
{
int l = 0,r=1e9, mid;
while(l+1<r)
{
mid=(l+r)>>1;
if(ok1(mid))
l=mid;
else
r=mid;
}
if(l>ans) ans = l;
}
cout << ans;
}
關(guān)鍵在于上面的ok函數(shù)的實(shí)現(xiàn)蔫耽，下面有兩個(gè)方法：
- 從左到右依次枚舉每一刀结耀，找到一個(gè)最小的i，使得左邊的四個(gè)子矩陣的和都不小于x匙铡，最終判定能不能連續(xù)切4次即可图甜，復(fù)雜度O(n)。代碼如下：
bool ok1(int x)
{
int T = 0,i,start = 0;
for(i=1;i<=n;i++)
{
if(sum(0,start,R1,i)>=x&&sum(R1,start,R2,i)>=x&&sum(R2,start,R3,i)>=x&&sum(R3,start,n,i)>=x)
{
T++;
start = i;
if(T==4) break;
}
}
return T == 4;
}
- 觀察上面的sum()函數(shù)鳖眼，容易發(fā)現(xiàn)每一刀切下后黑毅，其變化都是單調(diào)不降的。因此可以再次使用二分來(lái)找到這個(gè)i钦讳，進(jìn)一步降低時(shí)間復(fù)雜度為O(klogn)：
bool ok(int x)
{
int T = 4,l,r=0,mid,start;
while(T--)
{
start = r; l = r; r = m+1;
while(l<r)
{
mid = (l+r)>>1;
if(sum(0,start,R1,mid)>=x&&sum(R1,start,R2,mid)>=x&&sum(R2,start,R3,mid)>=x&&sum(R3,start,n,mid)>=x)
r=mid;
else
l=mid+1;
}
if(r==m+1) return 0;
}
return 1;
}
總結(jié)
1矿瘦、通過(guò)二分嵌套枕面，算法復(fù)雜度為枚舉O(n^3)O(log2(n))=O(n3log^2(n))*
2、注意到兩次二分的寫法匪凡，外層二分是求滿足條件的最大值膊畴，而內(nèi)層二分求的是滿足條件的最小值掘猿。
3病游、暴力美學(xué)，利用二分減少計(jì)算量稠通。
完整代碼如下
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<string>
#include<stack>
#include<set>
#define mem(f) memset(f,0,sizeof(f))
#define P2 pair<LL,LL>
typedef long long LL;
using namespace std;
const LL MOD = 1e9+7;
const int N = 85;
int n,m,R1,R2,R3;
string g[N];
int s[N][N];
void init()
{
int i,j;
for(i=0;i<n;i++)
cin >> g[i];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s[i][j]=g[i-1][j-1]-48+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
inline int sum(int x1,int y1,int x2,int y2)
{
return s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1];
}
bool ok(int x)
{
int T = 4,l,r=0,mid,start;
while(T--)
{
start = r; l = r; r = m+1;
while(l<r)
{
mid = (l+r)>>1;
if(sum(0,start,R1,mid)>=x&&sum(R1,start,R2,mid)>=x&&sum(R2,start,R3,mid)>=x&&sum(R3,start,n,mid)>=x)
r=mid;
else
l=mid+1;
}
if(r==m+1) return 0;
}
return 1;
}
void work()
{
int ans = 0;
for(R1=1;R1<n;R1++)
for(R2=R1+1;R2<n;R2++)
for(R3=R2+1;R3<n;R3++)
{
int l = 0,r=1e9, mid;
while(l+1<r)
{
mid=(l+r)/2;
if(ok(mid))
l=mid;
else
r=mid;
}
if(l>ans) ans = l;
}
cout << ans;
}
int main()
{
while(cin >> n >> m)
{
//cin >> A >> B;
init();
work();
}
return 0;
}
