成都网站建设 网络公司,重庆教育建设集团有限公司官方网站,唐河微网站建设,wordpress主题制作导航的n种方法[USACO11MAR] Brownie Slicing G
题目地址
P3017 [USACO11MAR] Brownie Slicing G
思路
二分最大化最小值 切割思路#xff1a; 一行一行进行切割#xff0c;如果这一行可以切割出b块大于等于mid的块#xff0c;就开始切割下一行 如果无法切割出b块#xff0c;就把正在…[USACO11MAR] Brownie Slicing G
题目地址
P3017 [USACO11MAR] Brownie Slicing G
思路
二分最大化最小值 切割思路 一行一行进行切割如果这一行可以切割出b块大于等于mid的块就开始切割下一行 如果无法切割出b块就把正在切割的行与下一行拼起来一起切割 最后通过能切割出b块的水平块块够不够a条来判断m是否合适 代码
#include iostreamusing namespace std;int a[1010][1010], s[1010][1010];
int r, c, x, y;bool check(int m) {int lrow 0;int rows 0;for (int i 1; i r; i ) {int num 0, sum 0;for (int j 1; j c; j ) {if (sum (s[i][j]-s[i][j-1])-(s[lrow][j]-s[lrow][j-1]) m)sum (s[i][j]-s[i][j-1])-(s[lrow][j]-s[lrow][j-1]);else {sum 0;num ;}}if (num y) {lrow i; rows;}}return rows x;
}int main() {cin r c x y;for (int i 1; i r; i )for (int j 1; j c; j ) {cin a[i][j];s[i][j] s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];}int left 0, right s[r][c];//m 越小越容易成功while (left right) {int m left right 1 1;if (check(m))left m;elseright m - 1;}cout left;return 0;
}
