GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版虽然算法竞赛入门经典书中标的是两个星号表示难度较高但是从方法和代码量上来看我觉得和两颗星的难度还差的比较远。当然或许是我直接看了书中的分析再做的缘故。参考书中的方式我的实现如下1. 首先计算每个格子向上连续的空地格数。一起计算的话只需要O(mn)即可。2. 然后是遍历每行再遍历每行中的每个元素计算最大的周长。3. 这里使用了一个链表存储这个元素前面元素的空地和格数根据一定规则调整和删除元素3.1. 如果当前格子是沼泽那么清空链表因为前面的所有元素都不能使用了。3.2. 如果当前元素的高度比之前的短那么之前的更长元素统一调整成当前元素的长度。因为如果要想组成矩形当前高度会作为之前元素的永远的限制。3.3. 如果某个元素的前面的元素要更高或者一样高那么这个元素没必要存在。即之前元素高度和你一样但是矩形长度比你更长因此不管后面走多少步都不会选择你。然后是遍历链表找到最大值并统计最后输出。AC代码#include stdio.h #include map #include list #define MAXMN 1005 using namespace std; int arr[MAXMN][MAXMN]; int m, n; // 当前格往上的连续最高格 int arrTop[MAXMN][MAXMN]; // 存放结果数据 mapint, int mp; void outputArr() { int i, j; for (i 0; i m; i) { for (j 0; j n; j) printf(%d, arrTop[i][j]); putchar(\n); } putchar(\n); } void getArrTop() { int i, j; for (i 0; i n; i) { arrTop[0][i] arr[0][i]; for (j 1; j m; j) { if (arr[j][i] 0) arrTop[j][i] 0; else arrTop[j][i] arrTop[j - 1][i] 1; } } } struct Node { int num, top; }; void printList(listNode ls) { for (auto ip ls.begin(); ip ! ls.end(); ip) { printf(top %d num %d\n, ip-top, ip-num); } } void computed(int line) { int i, j, maxV, value; listNode ls; auto ip ls.begin(), ipt ls.begin(); for (i 0; i n; i) { if (arr[line][i] 0) { // 清空list ls.clear(); continue; } Node no {i, arrTop[line][i]}; ls.push_back(no); // 统一调整限高 for (ip ls.begin(); ip ! ls.end(); ip) { if (ip-top no.top) ip-top no.top; } // 统一计算去掉的情况 ip ls.begin(), ipt ls.begin(); ip; while (ip ! ls.end()) { if (ip-top ipt-top) { ip ls.erase(ip); } else { ipt ip; ip; } } // 统一计算最大值 maxV 0; for (ip ls.begin(); ip ! ls.end(); ip) { value ip-top * 2 2 * (i - ip-num 1); if (maxV value) maxV value; } if (maxV ! 0) { if (!mp[maxV]) mp[maxV] 1; else mp[maxV]; } } } int main() { int t; int i, j; char c; scanf(%d, t); while (t--) { scanf(%d %d, m, n); for (i 0; i m; i) { getchar(); for (j 0; j n; j) { scanf(%c, c); if (c .) arr[i][j] 1; else arr[i][j] 0; } } getArrTop(); mp.clear(); for (i 0; i m; i) computed(i); for (auto ip mp.begin(); ip ! mp.end(); ip) { printf(%d x %d\n, ip-second, ip-first); } } return 0; }
و)
