36389

Luogu 1514 引水入城

链接:https://www.luogu.org/problem/P1514

思路:

搜索判断可行解,然后不难发现就是一个最少线段覆盖Question,使用类似$dp$的思路。

值得注意的是,在搜索中,记录左右能达到的地方,判断会有一些不同,具体请见代码。

代码:

#include <bits/stdc++.h> const int MAXN = 600; const int INF = 1 << 30; const int dirx[] = {0, -1, 0, 1}; const int diry[] = {1, 0, -1, 0}; using namespace std; int n, m, cnt1, ans, a[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN]; bool vis[MAXN][MAXN], flag; bool check(int x, int y) { return x < 1 || y < 1 || x > n || y > m; } void dfs(int x, int y) { for(int i = 0; i < 4; i++) { int dx = x + dirx[i], dy = y + diry[i]; if(check(dx, dy) || a[dx][dy] >= a[x][y]) continue; if(!vis[dx][dy]) { vis[dx][dy] = true; dfs(dx, dy); } l[x][y] = min(l[x][y], l[dx][dy]); r[x][y] = max(r[x][y], r[dx][dy]); } } int main() { cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> a[i][j]; l[i][j] = r[i][j] = j; } } for(int i = 1; i <= m; i++) { if(!vis[1][i]) { vis[1][i] = true; dfs(1, i); } } for(int i = 1; i <= m; i++) { if(!vis[n][i]) { flag = true; cnt1++; } } if(flag) { cout << "0" << endl << cnt1 << endl; return 0; } int lnow = 1, rnow = 0, last = 0; while(lnow <= m) { for(int i = last + 1; i <= m; i++) { if(l[1][i] <= lnow) { last = i; rnow = max(rnow, r[1][i]); } } ans++; lnow = rnow + 1; } cout << "1" << endl << ans << endl; return 0; }

来源:博客园

作者:BeyondLimits

链接:https://www.cnblogs.com/BeyondLimits/p/11425893.html

Recommend