首页 > 代码库 > UVA - 10558A Brief Gerrymander(递推)
UVA - 10558A Brief Gerrymander(递推)
题目大意:UVA - 10558A Brief Gerrymander(递推)
题目大意:给定一个100 * 100 的矩形,现在要求将这个区域划分,竖着的线已经给你划分好了,现在要求你在这个区域内再添加A个横着的线,1 100 这两条是一定要的,问怎样选择横着的线,能够使得选举区间最多。选举区间的条件:内部没有横竖线,并且有一个点在区间内部。注意:边界上的点也是算在内的,但是要防止重复计算到选区内。
解题思路:这题题意都不是那么好理解了,然后写起来复杂度也是很大的。参考了别人的题解:首先:dp[i][j]代表第i根横线的序号是j的时候,有多少个选区。S【i】【j】代表:第i根横线到第j根横线之间在已知竖线的情况下有多少个选区。注意这里因为要算边界的点,所以i到j是左闭右开【i,j)(包括i这线上的点,但是不包括j这条横线上的点)。dp【【i】【j】 =Max ( dp【i - 1】【k】 + s【k】【j】));
所以先要预处理出S【i】【j】:处理的时候也需要找个策略不然复杂度也是很高。用G【i】【j】【k】代表第i条横线到第j条横线和第i - 1竖线和第i条竖线是否是选取区。G【i】【j】【k】 |= G[i][j - 1][k];
G[i][j][k] |= t【j】【k】(第j - 1条直线上是否有点在K-1和k竖线之间,注意这里竖线的边界点也要计算,并且要防止重复。同理:【K -1 ,K)。
代码:
#include <cstdio> #include <cstring> const int N = 105; int n, m; int s[N][N]; int t[N][N]; int dp[N][N]; int p[N][N]; int street[N]; int G[N][N][N]; int path[N][N]; int Max (const int a, const int b) { return a > b ? a: b; } void init () { memset (t, 0, sizeof (t)); for (int i = 1; i <= 100; i++) { for (int j = 1; j < m; j++) { int k; for (k = street[j - 1]; k < street[j]; k++) if (p[i - 1][k]) break; if (k != street[j]) t[i][j] = 1; } } memset (G, 0, sizeof (G)); memset (s, 0, sizeof (s)); for (int i = 1; i < 100; i++) { for (int j = 1; j + i <= 100; j++) { for (int k = 1; k < m; k++) G[j][j + i][k] |= G[j][j + i - 1][k]; for (int k = 1; k < m; k++) G[j][j + i][k] |= t[j + i][k]; for (int k = 1; k < m; k++) if (G[j][j + i][k]) s[j][j + i]++; } } } void printf_ans (int A, int j) { if (path[A][j] == -1) return; printf_ans (A - 1, path[A][j]); printf (" %d", path[A][j]); } int main () { int x, y, A; while (scanf ("%d", &n) && n != -1) { memset (p, 0, sizeof (p)); for (int i = 0; i < n; i++) { scanf ("%d%d", &x, &y); p[y][x] = 1; } scanf ("%d", &m); for (int i = 0; i < m; i++) scanf ("%d", &street[i]); scanf ("%d", &A); init (); dp[1][1] = 0; path[1][1] = -1; for (int i = 2; i <= A; i++) { for (int j = i; j <= 100; j++) { dp[i][j] = 0; if (i == 2) { dp[i][j] = Max (dp[i][j] , dp[1][1] + s[1][j]); path[i][j] = 1; } else { for (int k = 2; k < j; k++) { if (dp[i - 1][k] + s[k][j] >= dp[i][j]) path[i][j] = k; dp[i][j] = Max (dp[i][j] , dp[i - 1][k] + s[k][j]); } } } } // printf ("%d\n", t[50][1]); printf ("%d", A); printf_ans(A, 100); printf (" 100\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。