uva 10558 - A Brief Gerrymander(记忆化搜索）
题目链接：10558 - A Brief Gerrymander
题目大意：在一个100 * 100的网格中， 给出n个坐标，坐标的含义为以该坐标为左下角的格子为neighborhood，对应给出坐标的顺序是street，后给的avenue（类似于x、y），然后给出k条切线将网格切成k -1块区域（avenue）头尾一定是1和100，然后在给出cut数，表是在street方向上可以切cut刀，然后将整个网格分成了若干块区域，要就含有neighborhood的区域数最多。对应的street方向的头尾也是1 和100，输出方案。
解题思路：先对坐标进行处理，用g[i][j]记录street为i，avenuei处于第j块，是否为neighborhood，然后用sum[i][j]叠加求和sum[i][j] = sum[i - 1][j] + g[i][j].在处理方面用递归求解。
给出案例：
3
5 5
6 16
9 10
3
1 15 100
4
输出：
4 1 6 11 100
如果输出是4 1 2 6 100表明坐标搞反了。
1
1 1
3 1 50 100
10
输出：
10 1 2 3 4 5 6 7 8 9 100
注意：求解时要注意剩下的行数要满足还需切的刀数。for (int i = top + 1; i <= 100 - cnt; i++)
#include <stdio.h>#include <string.h>const int N = 105;const int MAX = 10005;int x[MAX], y[MAX];int g[N][N], sum[N][N];int n, cut, k, dp[N][N], pace[N][N];void init() {memset(g, 0, sizeof(g));for (int i = 0; i < n; i++)scanf("%d%d", &x[i], &y[i]);int l[N];scanf("%d", &k);for (int i = 0; i < k; i++)scanf("%d", &l[i]);scanf("%d", &cut);for (int i = 0; i < n; i++) {int j;for (j = 1; j < k; j++)if (x[i] < l[j]) break;g[y[i] + 1][j] = 1;}for (int i = 1; i < N; i++)for (int j = 1; j < k; j++)sum[i][j] = sum[i - 1][j] + g[i][j];memset(dp, -1, sizeof(dp));}int solve(int top, int cnt) {int& ans = dp[top][cnt];if (ans > -1) return ans;int& rec = pace[top][cnt];ans = 0;rec = top + 1;if (cnt == 0) {for (int i = 1; i < k; i++)if (sum[100][i] - sum[top][i]) ans++;rec = 100;return ans;}for (int i = top + 1; i <= 100 - cnt; i++) {int num = 0;for (int j = 1; j < k; j++)if (sum[i][j] - sum[top][j]) num++;num += solve(i, cnt - 1);if (num > ans) {ans = num;rec = i;}}return ans;}void put(int cur, int cnt) {printf(" %d", cur);if (cnt < 0) return ;put(pace[cur][cnt], cnt - 1);}int main () {while (scanf("%d", &n), n > -1) {init();solve(1, cut - 2);printf("%d", cut);put(1, cut - 2);printf("\n");}return 0;}