解題區►解題區 - UVa

UVa 12795 - Ecology

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給 N x N 個 grid，每一格有權重，找到一個連通子圖，其大小恰好為 M，並且具有最大權重。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1

Sample Output

1
2
377
72

Solution

Number of fixed polyominoes with n cells.

Number of fixed polyominoes with n cells. (Formerly M1639 N0641)
1, 2, 6, 19, 63, 216, 760, 2725, 9910, 36446, 135268, 505861, 1903890, 7204874, 27394666, 104592937, 400795844, 1540820542, 5940738676, 22964779660, 88983512783, 345532572678, 1344372335524, 5239988770268, 20457802016011, 79992676367108, 313224032098244, 1228088671826973

連通子圖 n = 10 也不過 36446，對於所有位置嘗試擺放，也不過 O(36446 * 50 * 50)，給 60 秒還跑不出來。

關於窮舉連通圖的部分，想像成生成樹，這棵樹必然要有 M 個節點，適時要在葉節點返回，然後在其他尚未長出來的地方繼續生長。根據尤拉路徑最多走 2M 步，窮舉 2M 步進行建造。

為了加快窮舉速度，將找到的 polyominoes 依據長寬儲存，窮舉時先 greedy 估算這個矩形內部能產出最好的 polyominoes 可能是多少，如果已經低於已知解就直接放棄。

只能說測資不隨機，有極端測資，照理來講不用建表的速度應該會稍微快了些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
#include <set> 
#include <string.h>
#include <assert.h>
using namespace std;
int g[64][64], n, m;
int used[64][64];
pair<int, int> path[64], pre[64][64];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct Area {
	vector<pair<int, int> > V;
	bool operator<(const Area &a) const {
		for (int i = 0; i < V.size(); i++) 
			if (V[i] != a.V[i])	return V[i] < a.V[i];
		return false;
	}
	Area() {
		V.clear();
	}
};
// Number of fixed polyominoes with n cells. https://oeis.org/A001168
set<Area> shape[16][16][16];
void storeArea(Area a) {
	sort(a.V.begin(), a.V.end());
	int x, y, mx, my;
	x = a.V[0].first, y = a.V[0].second;
	mx = x, my = y;
	for (int i = 0; i < a.V.size(); i++) {
		x = min(x, a.V[i].first), y = min(y, a.V[i].second);
		mx = max(mx, a.V[i].first), my = max(my, a.V[i].second);
	}
	for (int i = 0; i < a.V.size(); i++)
		a.V[i].first -= x, a.V[i].second -= y;
	sort(a.V.begin(), a.V.end());
	shape[a.V.size()][mx - x][my - y].insert(a);
	assert(mx - x >= 0 && mx - x < 16 && my - y >= 0 && my - y < 16);
}
void dfs(int idx, int x, int y, int pick, int m) {
	if (pick == m) {
		Area t;
		for (int i = 0; i < pick; i++)
			t.V.push_back(path[i]);
		storeArea(t);
		return ;
	}
	if (idx >= 2 * m)
		return;
	vector< pair<int,int> > test;
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i], 
			ty = y + dy[i];
		if (used[tx][ty])
			continue;
		pre[tx][ty] = make_pair(x, y);
		path[pick] = make_pair(tx, ty);
		used[tx][ty] = 1;
		dfs(idx+1, tx, ty, pick + 1, m);
		test.push_back(make_pair(tx, ty));
	}
	if (pre[x][y].first != -1) // stop on leaf
		dfs(idx+1, pre[x][y].first, pre[x][y].second, pick, m);
	for (int i = 0; i < test.size(); i++) {
		int tx = test[i].first,
			ty = test[i].second;
		used[tx][ty] = 0;
	}
}
int place(int x, int y, int n, const Area &a) {
	int ox = x, oy = y;
	int sum = 0;
	for (int i = 0; i < a.V.size(); i++) {
		x = ox + a.V[i].first;
		y = oy + a.V[i].second;
		if (x < 0 || y < 0 || x >= n || y >= n)	return 0;
		sum += g[x][y];
	}
	return sum;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	for (int i = 1; i <= 10; i++) {
		for (int j = 0; j < 32; j++)
			for (int k = 0; k < 32; k++)
				pre[j][k] = make_pair(-1, -1);
		pre[11][11] = make_pair(-1, -1);
		path[0] = make_pair(11, 11);
		used[11][11] = 1;
		dfs(1, 11, 11, 1, i);
		used[11][11] = 0;
		int sum = 0;
		for (int j = 0; j < i; j++) {
			for (int k = 0; k < i; k++)
				sum += shape[i][j][k].size();
		} 
//		printf("complete %d %d\n", i, sum);
	}
	while (scanf("%d %d", &n, &m) == 2) {
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &g[i][j]);
			}
		}
		
		int ret = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int mx[16] = {}, mxx = 0, tmp;
				for (int p = 0; p < m && i + p <= n; p++) {
					mxx = 0;
					for (int q = 0; q < m && j + q <= n; q++) {
						mx[q] = max(mx[q], g[i+p][j+q]);
						mxx = max(mxx, mx[q]);
						if (mxx * m <= ret)	continue;
						vector<int> D;
						for (int a = i; a <= i+p; a++)
							for (int b = j; b <= j+q; b++) 
								D.push_back(g[a][b]);
						sort(D.begin(), D.end(), greater<int>());
						tmp = 0;
						for (int a = 0; a < m; a++)
							tmp += D[a];
						if (tmp <= ret)		continue;
						for (set<Area>::iterator it = shape[m][p][q].begin(); 
							it != shape[m][p][q].end(); it++) {
							ret = max(ret, place(i, j, n, *it));
						}
					}
				}
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
/*
5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1
3 5
0 5 0
5 5 5
0 5 0
10 5
733 950 26 696 512 570 327 531 829 600 
499 459 728 877 673 464 368 438 566 599 
512 631 242 499 919 931 688 602 490 172 
587 745 704 453 475 370 47 439 705 844 
133 449 264 732 361 612 196 635 739 853 
944 872 938 228 74 296 604 677 801 27 
763 628 650 40 558 159 7 500 405 423 
450 455 26 543 881 87 292 431 74 546 
349 115 568 589 390 40 606 802 434 479 
732 890 361 334 208 439 118 18 494 894 
*/