洛谷1941（dp）

常规的dp，当前有值且碰不到管子就转移，可以连跳的操作我就加了一维表示当前是不是连跳过来的。第二问前缀和即可得（不对啊边走边记录就行了吧我冗了Orz）。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e4 + 5, maxm = 1e3 + 5;

const int inf = 0x3f3f3f3f;

int n, m, k;

int dp[maxn][maxm][2], cnt[maxn];

pair<int, int> go[maxn], limit[maxn];

int Judge() {

	int res = inf;

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

		res = min(res, dp[n][j][0]);

	}

	return res;

}

int main() {

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

	for (int i = 0; i < n; i++) {

		int up, down;

		scanf("%d %d", &up, &down);

		go[i] = {up, down};

		limit[i] = {1, m};

	}

	limit[n] = {1, m};

	for (int i = 0; i < k; i++) {

		int j, l, r;

		scanf("%d %d %d", &j, &l, &r);

		limit[j] = {l + 1, r - 1};

		cnt[j]++;

	}

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

		for (int j = 0; j <= m; j++){

			dp[i][j][0] = dp[i][j][1] = inf;

		}

	}

	for (int i = 0; i < n; i++) {

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

			for (int k = 0; k <= 1; k++) {

				if (dp[i][j][k] != inf) {

					int high = min(j + go[i].first, m);

					if (high >= limit[i + 1].first && high <= limit[i + 1].second)

                        dp[i + 1][high][0] = min(dp[i + 1][high][0], dp[i][j][k] + 1);

					dp[i][high][1] = min(dp[i][high][1], dp[i][j][k] + 1);

					int low = j - go[i].second;

					if (!k && low >= limit[i + 1].first && low <= limit[i + 1].second)

                        dp[i + 1][low][0] = min(dp[i + 1][low][0], dp[i][j][k]);

				}

			}

		}

	}

	int ans = Judge();

	if (ans == inf) {

		for (int i = n - 1; i >= 0; i--) {

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

				if (dp[i][j][0] != inf) {

					for (int t = 1; t <= n; t++)	cnt[t] += cnt[t - 1];

					printf("0\n%d\n", cnt[i]);

					return 0;

				}

			}

		}

	} else {

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

	}

	return 0;

}

巴特西

洛谷1941（dp）

最新文章

热门文章