【NOIP2010】引水入城 题解(Probably)

题目传送门:!点我传送!

知识点:广度优先搜索+区间最小覆盖

题目大意就是给我们一张图,我们只能从第一行的任意位置出发,走一条高度递减的路径到最后一行,要求我们达到最后一行的每一个位置。问我们最少要走几条路,若无法达到最后一行的全部位置则要求输出有几个位置我们无法到达。

首先我们先对题目进行分析,因为流水路径是连续的,所以对于在可以到达最后一行每个位置的情况下,第一行某个位置作为起点,则其能到达最后一行的位置势必是连续的,不理解的可以自己画图举反例看看。对于每个起点所到最后一行我们可以看做是一个范围是[L,R]的区间,那接着我们只要求出哪几个区间能将总区间覆盖并使使用的区间最少,这就是区间最小覆盖问题。

  • 对于找第一行所对应很明显我们只要用广度优先搜索找出其对应的区间即可。但在这要注意要进行剪枝,不然讲道理是会被卡一个点的。因为每个点所能流到位置是固定的,所以如果X点能到达Y点,那X点也能到达Y所能到达的点。所以对于第一行我们只要对凸出来的最高点进行广搜。
    
    
    1
    2
    3
    4
    5
        for (i = 1; i <= m; i++)
        {
            if (map[1][i]<map[1][i+1]||map[1][i]<map[1][i-1]) continue;//判断是否有其他点可以流到该点
            ji[++ji[0]] = i; //将凸出的点记录到数组中
        }
  • 在已知第一行的范围后,我们只要跑一遍区间最小覆盖问题即可。
  • 用一个数组f[i]记录以i为左端点的区间能覆盖的最大距离,再用一个数组Ans记录能覆盖这个点的且向右距离最大的区间的右端点。最后再根据Ans让每个取得查询尽量靠右,统计取得区间个数即为最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    Ans[1] = f[1];
    for(i = 2; i <= m; i++)
    {  
        if(Ans[i-1]>f[i])  
        {  
            Ans[i] = Ans[i-1];  
        }  
        else  
        {  
            Ans[i]=f[i];  
        }  
    }  
   
    i = 1;
    int sum = 0;
    while (i<=m)
    {
        i = Ans[i]+1;
        sum++;
    }

以下为完整代码:


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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};

int map[510][510];
int path[510][510];
int ji[510],ok[510];
int n, m;

struct sd
{
    int x, y;
}dui[500510];

struct sd1
{
    int L, R;
}range[510];

void BFS(int sdx)
{
    dui[1].x = 1;
    dui[1].y = sdx;
    path[1][sdx] = 1;
    int t = 1, w = 1;
    while (w >= t)
    {
        for (int k = 0; k < 4; k++)
        {
            int px = dx[k] + dui[t].x;
            int py = dy[k] + dui[t].y;
           
            if (px>=1&&px<=n&&py>=1&&py<=m)
            {
                if (map[px][py]>=map[dui[t].x][dui[t].y]||path[px][py]) continue;
                dui[++w].x = px; dui[w].y = py;
                path[px][py] = 1;
                if (px==n)
                {
                    if (!ok[py])
                    {
                        ok[py] = 1;
                        ok[0]++;
                    }
                    range[sdx].L = py < range[sdx].L||range[sdx].L == 0 ? py :range[sdx].L;
                    range[sdx].R = py > range[sdx].R||range[sdx].R == 0 ? py :range[sdx].R;
                }
            }
        }
        t++;
    }
   
}


int f[510],Ans[510];
int main(void)
{
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 1; i <=n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
   
    for (i = 1; i <= m; i++)
    {
        if (map[1][i]<map[1][i+1]||map[1][i]<map[1][i-1]) continue;
        ji[++ji[0]] = i;
    }
    if (n == 1)
    {
        printf("1\n%d", ji[0]);
        return 0;
    }
   
    for (i = 1; i <= ji[0]; i++)
    {
        memset(path,0,sizeof(path));
        if (path[1][ji[i]]) continue;
        BFS(ji[i]);
        f[range[ji[i]].L] = f[range[ji[i]].L] < range[ji[i]].R ? range[ji[i]].R :f[range[ji[i]].L];
    }
    if (ok[0] < m)
    {
        printf("0\n%d", m-ok[0]);
        return 0;
    }
   
    Ans[1] = f[1];
    for(i = 2; i <= m; i++)
    {  
        if(Ans[i-1]>f[i])  
        {  
            Ans[i] = Ans[i-1];  
        }  
        else  
        {  
            Ans[i]=f[i];  
        }  
    }  
   
    i = 1;
    int sum = 0;
    while (i<=m)
    {
        i = Ans[i]+1;
        sum++;
    }
    printf("1\n%d", sum);
    return 0;
}

1
 

发表评论

邮箱地址不会被公开。 必填项已用*标注