uva1580

题意：给定一个水池，水池每个格子都有深度，给出a,b使得放入水池的矩形长，宽不超过a,b。找出一个矩形，使得体积最大

分析：暴力可以过，但是有很多其他解法，比如二分体积，枚举位置；或者是以深度为搜索对象，相同的深度格子连接起来，这种方法要要考虑一些细节。

#includeusing namespace std;#define rep(i,x,y) for(int i=x;i=arep(i, 0, m) {//枚举起始横坐标rep(j, 0, n) {//枚举起始纵坐标memset(dep, 0x3f, sizeof(dep));rep(r, i, m) {int aa = r - i + 1;if (aa > b)break;rep(c, j, n) {int bb = c - j + 1;if (bb > b || min(bb, aa) > a)break;dep[c] = min(dep[c], d[r][c]);if (c)dep[c] = min(dep[c - 1], dep[c]);V = 1LL * aa*bb*dep[c];S = 1LL * aa*bb;ans = max(ans, 1LL * (V / (n*m - S) + dep[c] - (V % (n*m - S) == 0))*S);}}}}printf("%lld\n", ans);}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！