1. 题目

传送门=￣ω￣=

2. 题解

我就是来混更的别打我啊 OvO

（要找借口也不是没有——在很久很久以前我看到这题觉得好难啊然后就一直没做今天补了一个千年老坑是吧就发混更一下了）

而且由于我太菜了，已经是傻逼普及组选手了所以我看了题解才会的，我还是好好的当普及组选手吧这样混更更方便

由题解可知，从第一行的某个城市出发能遍历到的最后一行的城市集合一定是一个连续区间，如果出现不连续情况就说明断开的部分无法被遍历，无解。

那么计算这个区间就用记忆化搜索

$L(i, j)=min(L(next _ i, next _ j))$
$R(i, j)=max(R(next _ i, next _ j))$

复杂度 $O(n^2)$

如果最后一行都能被第一行遍历到，那么问题就成了给你一个长度为 $n$的区间和一堆小区间，问你最少选多少个小区间使得被选的小区间覆盖了整个长度为 $n$的区间。

排个序单调栈搞搞就行了，复杂度 $O(nlog _ 2 n)$

这么说总复杂度还是 $O(n ^ 2)$，真不知道为什么出题人只开到 $500$的数据。。。

代码：

#include <bits/stdc++.h>

#define NS (505)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

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

int n, m, h[NS][NS], l[NS][NS], r[NS][NS];

void Dfs(int a, int b)
{
    if (l[a][b]) return;
    l[a][b] = INT_MAX, r[a][b] = INT_MIN;
    if (a < 1 || a > n || b < 1 || b > m) return;
    if (a == n) l[a][b] = r[a][b] = b;
    for (int i = 0; i < 4; i += 1)
        if (h[a][b] > h[a + dx[i]][b + dy[i]])
        {
            Dfs(a + dx[i], b + dy[i]);
            l[a][b] = min(l[a][b], l[a + dx[i]][b + dy[i]]);
            r[a][b] = max(r[a][b], r[a + dx[i]][b + dy[i]]);
        }
}

PII e[NS], st[NS];

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= m; j += 1)
            IN(h[i][j]);
    for (int i = 1; i <= m; i += 1) Dfs(1, i);
    int cnt = 0;
    for (int i = 1; i <= m; i += 1) if (!l[n][i]) cnt++;
    if (cnt) printf("0\n%d\n", cnt), exit(0);
    for (int i = 1; i <= m; i += 1) e[i].FIR = l[1][i], e[i].SEC = r[1][i];
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; i += 1)
        if (e[i].FIR <= e[i].SEC)
        {
            if (e[i].FIR == 1) st[cnt = 1] = e[i];
            else
            {
                if (e[i].SEC <= st[cnt].SEC) continue;
                while (cnt >= 2 && st[cnt - 1].SEC + 1 >= e[i].FIR) cnt--;
                st[++cnt] = e[i];
            }
        }
    printf("1\n%d\n", cnt);
    return 0;
}