蛋糕

gmoj 3918

題目大意：

有一個蛋糕，分成$n?m$個單位，現在橫豎各切三刀，使其分成16個矩陣，使價值最小的矩陣價值最大

輸出樣例

5 5 95998 21945 23451 99798 74083

輸入樣例

3

數據范圍

40%的數據， 4 <= R,C <= 10。
60%的數據， 4 <= R,C <= 20。
100%的數據， 4 <= R,C <= 75。

樣例解釋

解題思路：

二分答案
然后枚舉豎著怎樣切，最后判斷可不可以切
時間復雜度$o(m^{3}nlogSum)$

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n, m, l, r, k, mid, num, a[100][100]; char x; int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j){cin>>x;a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + x - 48;//前綴和r += x - 48;}l = 1;while (l < r){num = 0;mid = (l + r + 1) >> 1;for (int c1 = 1; c1 <= m - 3 && num < 4; ++c1)//枚舉怎么切for (int c2 = c1 + 1; c2 <= m - 2 && num < 4; ++c2)for (int c3 = c2 + 1; c3 <= m - 1 && num < 4; ++c3){k = 1;num = 0;for (int i = 1; i <= n; ++i)if (a[i][c1] - a[k - 1][c1] >= mid && a[i][c2] - a[k - 1][c2] - a[i][c1] + a[k - 1][c1] >= mid && a[i][c3] - a[k - 1][c3] - a[i][c2] + a[k - 1][c2] >= mid && a[i][m] - a[k - 1][m] - a[i][c3] + a[k - 1][c3] >= mid) //是否每一行的四個矩陣都大于mid了{k = i + 1;//切開num++;}}if (num >= 4) l = mid;//是否滿足else r = mid - 1; }printf("%d", l); }

總結

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

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