正題

題目鏈接:https://jzoj.net/senior/#contest/show/2953/0

---

題目大意

$n?m$的矩陣，有數字，橫著三刀豎著三刀分成16份使得最小那份最大。

---

解題思路

暴力枚舉豎著的三刀，然后二分答案判定即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=80; int n,m,a[N][N],lim,ans; bool check(int c1,int c2,int c3,int x) {int p1=0,p2=0,p3=0,p4=0,k=0;for(int i=1;i<=n;i++){p1+=a[i][c1];p2+=a[i][c2]-a[i][c1];p3+=a[i][c3]-a[i][c2];p4+=a[i][m]-a[i][c3];if(p1>=x&&p2>=x&&p3>=x&&p4>=x)p1=p2=p3=p4=0,k++;}return k>=4; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%1d",&a[i][j]);lim+=a[i][j];a[i][j]+=a[i][j-1];}for(int c1=1;c1<=m;c1++)for(int c2=c1+1;c2<=m;c2++)for(int c3=c2+1;c3<=m;c3++){int l=0,r=lim;while(l<=r){int mid=(l+r)/2;if(check(c1,c2,c3,mid)) l=mid+1;else r=mid-1;}ans=max(ans,r); }printf("%d",ans); }

總結

以上是生活随笔為你收集整理的jzoj3918-蛋糕【二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。