本文主要是介绍uva 12265 - Selling Land(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 12265 - Selling Land
题目大意：给出一个图，要求以每个位置为右下角，找出最大周长的矩阵，然后统计所有周长的矩阵。
解题思路：首先可以维护每个位置向上的最大生长高度，然后按照每一行去枚举列，维护一个单调队列，使得高度递增，以及长度最优（在添加的那步进行控制）。对于每个新的长度，将比它高的直接忽略。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>using namespace std;
const int N = 1e3+5;
typedef pair<int, int> pi;int n, m, v[N][N], ans[2*N];void init() {char str[N];memset(v, 0, sizeof(v));memset(ans, 0, sizeof(ans));scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%s", str+1);for (int j = 1; j <= m; j++) {if (str[j] == '#') v[i][j] = 0;else v[i][j] = v[i-1][j] + 1;}}
}void solve () {for (int i = 1; i <= n; i++) {stack<pi> s;for (int j = 1; j <= m; j++) {int p = j;while (!s.empty() && s.top().first >= v[i][j]) {p = s.top().second;s.pop();}if (!v[i][j]) continue;if (s.empty() || v[i][j] - s.top().first > p - s.top().second) {ans[v[i][j] + j - p + 1]++;s.push(make_pair(v[i][j], p));} else ans[s.top().first + j - s.top().second + 1]++;}}for (int i = 1; i <= n + m; i++) {if (ans[i]) printf("%d x %d\n", ans[i], i * 2);}
}int main () {int cas;scanf("%d", &cas);while (cas--) {init();solve();}return 0;
}
这篇关于uva 12265 - Selling Land(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
