NOIP2010提高组.引水入城

*前置题目

901. 滑雪

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310, INF = 0x3f3f3f3f;
const int dx[4] = {
   0, -1, 0, 1}, dy[4] = {
   1, 0, -1, 0};

int n, m, h[N][N];
int f[N][N];
int ans;

int dfs(int x, int y) {
   
	if (f[x][y] != -1) return f[x][y];
	f[x][y] = 1;

	for (int i = 0; i < 4; ++i) {
   
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > m || h[nx][ny] >= h[x][y]) continue;
		int son = dfs(nx, ny);
		f[x][y] = max(f[x][y], son + 1);
	}

	return f[x][y];
}

int main() {
   
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			cin >> h[i][j];
		}
	}

	memset(f, -1, sizeof f);
	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			if (f[i][j] == -1) ans = max(ans, dfs(i, j));
		}
	}

	cout << ans << "\n";
	return 0;
}

907. 区间覆盖

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int s, e, n;
struct Seg {
   
	int l, r;
	bool operator< (const Seg &s) const {
   
		return l < s.l;
	}
} segs[N];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> s >> e >> n;
	for (int i = 0; i < n; ++i) cin >> segs[i].l >> segs[i].r;
	sort(segs, segs + n);

	int ans = 0;
	for (int i = 0; i < n;) {
   
		int r = -INF;
		while (i < n && segs[i].l <= s) {
   
			r = max(r, segs[i].r);
			i++;
		}
		ans++;
		if (r < s) {
   
			cout << -1 << "\n";
			return 0;
		}
		if (r >= e) {
   
			cout << ans << "\n";
			return 0;
		}
		s = r;
	}

	cout << -1 << "\n";
	return 0;
}

题目

497. 引水入城

算法标签: 记忆化搜索, 贪心, $dp$

思路

发现每个水库覆盖的城市必须是连续的, 因为如果不连续, 其他地方的水也无法连接到当前城市, 因此问题就转化为了最少需要多少区间能将最后的城市全部覆盖?

也就是经典的区间覆盖问题, 计算每个第一层的城市可以覆盖哪些最后一层的城市可以记忆化搜索求解

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
const int dx[4] = {
   -1, 0, 1, 0}, dy[4] = {
   0, 1, 0, -1};

int n, m, h[N][N];
struct Seg {
   
	int l, r;

	bool operator<(const Seg &s) const {
   
		return l < s.l;
	}
} f[N][N];

void dfs(int x, int y) {
   
	auto &p = f[x][y];
	if (p.l != -1) return;

	p.l = N;
	if (x == n) p = {
   y, y};
	for (int i = 0; i < 4; ++i) {
   
		int nx = x + dx[i], ny = y + dy[i];;
		if (nx < 1 || nx > n || ny < 1 || ny > m || h[nx][ny] >= h[x][y]) continue;
		dfs(nx, ny);
		p.l = min(p.l, f[nx][ny].l);
		p.r = max(p.r, f[nx][ny].r);
	}

}

int main() {
   
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			cin >> h[i][j];
		}
	}

	memset(f, -1, sizeof f);
	for (int i = 1; i <= m; ++i) dfs(1, i);

	int cnt = 0;
	for (int i = 1; i <= m; ++i) {
   
		if (f[n][i].l == -1) cnt++;
	}

	if (cnt) {
   
		cout << 0 << "\n";
		cout << cnt << "\n";
		return 0;
	}

	vector<Seg> vec;
	for (int i = 1; i <= m; ++i) vec.push_back(f[1][i]);
	sort(vec.begin(), vec.end());

	int ans = 0;
	for (int i = 0, s = 1; i < m;) {
   
		int r = 0;
		while (i < m && vec[i].l <= s) {
   
			r = max(r, vec[i].r);
			i++;
		}
		ans++;
		if (r >= m) break;
		s = r + 1;
	}

	cout << 1 << "\n";
	cout << ans << "\n";
	return 0;
}