[题解？]NOIP2014飞扬的小鸟

发表于 | 评论数： | 阅读次数：
本文字数： 4k | 阅读时长 ≈ 4 分钟

题目描述

洛谷

题解？

dp方程还是比较好推的吧……但是有一些细节需要注意。

这是我一开始80分的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , m , k;
int x[10010] , y[10010];
int dp[10010][1010];
int l[10010] , h[10010];

int main()
{
	n = read() , m = read() , k = read();
	for(int i = 1; i <= n; i ++)
	  x[i] = read() , y[i] = read();
	for(int i = 0; i <= n; i ++) for(int j = 0; j <= m; j ++) dp[i][j] = 2e9;
	for(int i = 1; i <= k; i ++)
	{
		int p = read();
		l[p] = read() , h[p] = read();
	}
	for(int i = 0; i <= n; i ++) 
	{
		if(!h[i]) h[i] = m + 1;
	}
	for(int i = l[0] + 1; i < h[0]; i ++) dp[0][i] = 0;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = l[i] + 1; j < h[i]; j ++)
		{
			if(j == m)
			  for(int q = x[i]; q >= 0; q --) dp[i][j] = min(dp[i][j] , min(dp[i - 1][m - q] , dp[i][m - q]) + 1);
			if(j > x[i]) dp[i][j] = min(dp[i][j] , min(dp[i - 1][j - x[i]] , dp[i][j - x[i]]) + 1);
			if(j + y[i] <= m) dp[i][j] = min(dp[i][j] , dp[i - 1][j + y[i]]);  
		}
	}
	int ans = 2e9;
	for(int i = l[n] + 1; i < h[n]; i ++) ans = min(ans , dp[n][i]);
	if(ans < 2e9)
	{
		printf("1\n%d\n" , ans);
	}
	else
	{
		printf("0\n");
		for(int i = n - 1; i >= 0; i --)
		{
			for(int j = l[i] + 1; j < h[i]; j ++)
			  ans = min(ans , dp[i][j]);
			if(ans < 2e9)
			{
				int tot = 0;
				for(int kk = 0; kk <= i; kk ++) if(h[kk] <= m) tot ++;
				printf("%d\n" , tot);
				return 0;
			}
		}
	}
	return 0;
}

80分的原因主要是在转移时出现错误，在洛谷这篇讨论中有详细的解答

链接

主要是由于我在转移的时候只考虑在管道间的高度，这样会导致忽略了一些中间的情况，如下面这组样例

1
2
3
4
5
6
3 1000 2
2 1
2 1
2 1
1 1 10
2 980 990

在第二个管道转移时由于我只枚举了$980$~$990$,导致$980$之前$dp$值全为inf，无法转移，但事实上小鸟可以多次跳跃，前面的值同样可以用来转移。

解决方法是先将高度全部枚举一遍，最后再把$0$~$l$和$h$~$m$的值赋为inf

果然我还是太菜了啊……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , m , k;
int x[10010] , y[10010];
int dp[10010][2010];
int l[10010] , h[10010];

int main()
{
	n = read() , m = read() , k = read();
	for(int i = 1; i <= n; i ++)
	  x[i] = read() , y[i] = read();
	for(int i = 0; i <= n; i ++) for(int j = 0; j <= 2 * m; j ++) dp[i][j] = 2e9;
	for(int i = 1; i <= k; i ++)
	{
		int p = read();
		l[p] = read() , h[p] = read();
	}
	for(int i = 0; i <= n; i ++) 
	{
		if(!h[i]) h[i] = m + 1;
	}
	for(int i = l[0] + 1; i < h[0]; i ++) dp[0][i] = 0;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = x[i] + 1; j <= x[i] + m; j ++) 
		{
			dp[i][j] = min(dp[i][j] , min(dp[i - 1][j - x[i]] , dp[i][j - x[i]]) + 1);
		}
		for(int j = m + 1; j <= x[i] + m; j ++) dp[i][m] = min(dp[i][m] , dp[i][j]);
		for(int j = l[i] + 1; j < h[i]; j ++) if(j + y[i] <= m) dp[i][j] = min(dp[i - 1][j + y[i]] , dp[i][j]);
		for(int j = 0; j <= l[i]; j ++) dp[i][j] = 2e9;
		for(int j = h[i]; j <= m; j ++) dp[i][j] = 2e9;
	}
	int ans = 2e9;
	for(int i = l[n] + 1; i < h[n]; i ++) ans = min(ans , dp[n][i]);
	if(ans < 2e9)
	{
		printf("1\n%d\n" , ans);
	}
	else
	{
		printf("0\n");
		for(int i = n - 1; i >= 0; i --)
		{
			for(int j = l[i] + 1; j < h[i]; j ++)
			  ans = min(ans , dp[i][j]);
			if(ans < 2e9)
			{
				int tot = 0;
				for(int kk = 0; kk <= i; kk ++) if(h[kk] <= m) tot ++;
				printf("%d\n" , tot);
				return 0;
			}
		}
	}
	return 0;
}