P1950 长方形
2022/3/30 23:20:06
本文主要是介绍P1950 长方形,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
以行为单位,统计以第k行为底边的矩形数量,而对于每一行,以每一格为基准计算左方案 li,右方案 ri,高方案 hi。同时为了防止重复计算,左方案 li 为这一列左边满足h值小于等于 hi 的列号(没有的话为0),右方案 ri 为这一列右边第一个满足h值小于hi的列号(如果没有的话就为col+1)。而以这样为基准的每一个小方块的矩阵的数量为(i-li)*(ri-i)*hi。(这样的方法在类似的求矩形数量的题目中都是一种高效的算法)在计算左右方案时为降低复杂度,需要用到单调栈。
#include<iostream> #define MAXN 1010 using namespace std; int h[MAXN], r[MAXN], l[MAXN], st[MAXN]; long long ans; char G[MAXN][MAXN]; int main(void) { int n = 0, m = 0, top = 0; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> G[i][j]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) h[j] = G[i][j] == '*' ? 0 : h[j] + 1; for (int j = 1; j <= m; j++) { while (top > 0 && h[j] < h[st[top]]) { r[st[top]] = j; top--; } top++; st[top] = j; } while (top > 0) { r[st[top]] = m + 1; top--; } for (int j = m; j >= 1; j--) { while (top > 0 && h[j] <= h[st[top]]) { l[st[top]] = j; top--; } top++; st[top] = j; } while (top > 0) { l[st[top]] = 0; top--; } for (int j = 1; j <= m; j++) ans += (j - l[j]) * (r[j] - j) * h[j]; } cout << ans; return 0; }
这篇关于P1950 长方形的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性