洛谷P1514引水入城

题目

搜索加贪心其实并不需要用到\(DP\),搜索也是比较简单地搜索。

对于每个第一行的城市进行类似于滑雪那道题的搜索，然后记录最后一行它所覆盖的区间，易得一个一行城市只会有一个区间。然后可以在最后进行线段覆盖贪心即可求出答案。要注意区间闭开和边界问题。

\(Code\)

#include <bits/stdc++.h>

#define N 501

using namespace std;

int di[5] = {0, 1, -1, 0, 0}; int dj[5] = {0, 0, 0, 1, -1};

int n, m, flag, tot, data[N][N], vis[N], dp[N][N];

struct C7 {

	int i, j;

};

struct block {

	int l, r;

}s[100010];

bool cmp(block a, block b)

{

	if (a.l == b.l)

		return a.r > b.r;

	return a.l < b.l;

}

inline void init()

{

 	scanf("%d%d", &n, &m);

 	for (int i = 1; i <= n; i++)

 		for (int j = 1; j <= m; j++)

  			scanf("%d", &data[i][j]);

}

inline void bfs()

{

 	queue <C7> q;

 	for (int o = 1; o <= m; o++)

 	{

 		memset(dp, 0, sizeof(dp));

 		if (n == 1)	vis[o] = 1;

 		dp[1][o] = o;

 		q.push({1, o});

 		while (!q.empty())

 		{

 		 	C7 cur = q.front(); q.pop();

 		 	int i = cur.i, j = cur.j;

		 	for (int k = 1; k <= 4; k++)

		 	{

		 	 	int nexi = i + di[k], nexj = j + dj[k];

		 	 	if (nexi <= 0 || nexj <= 0 || nexi > n 	|| nexj > m)

		 		 	continue;

		 	 	if (!dp[nexi][nexj] && data[nexi][nexj] < data[i][j])

		 	 	{

		 		 	dp[nexi][nexj] = o;

		 		 	q.push({nexi, nexj});

		 		 	if (nexi == n)

		 	 	 		vis[nexj] = 1;

		 	 	}

		 	}

	 	}

	 	flag = 0;

	 	for (int i = 1; i <= m + 1; i++)

	 	{

		 	if (dp[n][i] && !flag)

		 	{

		 		flag = 1;

		 		s[++tot].l = i;

		 	}

		 	if (!dp[n][i] && flag)

		 	{

		 		s[tot].r = i;

		 		flag = 0;

		 	}

		}

 	}

}

inline void prin()

{

 	int ans = 0;

 	for (int j = 1; j <= m; j++)

 		if (vis[j])

 			ans++;

 	if (ans != m)

 		printf("0\n%d", m - ans);

 	else

 	{

 		sort(s + 1, s + 1 + tot, cmp);

// 		for (int i = 1; i <= tot; i++)

// 			printf("%d %d\n", s[i].l, s[i].r);

// 		return;

 		int ans = 0, left = 0, right = 0;

	 	for (int i = 1; i <= tot; i++)

	 	{

			if (left >= s[i].l)//要加=号，这是贪心的线段覆盖的模板。

			right = max(right, s[i].r);

			else

		 	{

				ans++;

				left = right;

				right = max(right, s[i].r);

		 	}

			if (right > m) break;

		}

 		printf("1\n%d", ans);

 	}

}

int main()

{

	init();

 	bfs();

 	prin();

 	return 0;

}

巴特西

洛谷P1514引水入城

最新文章

热门文章