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. 引水入城
在這里插入圖片描述

算法標簽: 記憶化搜索, 貪心, $d p$

思路

發現每個水庫覆蓋的城市必須是連續的, 因為如果不連續, 其他地方的水也無法連接到當前城市, 因此問題就轉化為了最少需要多少區間能將最后的城市全部覆蓋?

也就是經典的區間覆蓋問題, 計算每個第一層的城市可以覆蓋哪些最后一層的城市可以記憶化搜索求解

代碼

#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;
}