Oiclass P1993 题解

又是一道 DP

看到题目，我的第一反应就是：这鼹鼠是什么玩意儿？

额，\(\Huge 搞错了\) 再来

下面是传统的五步

1. 划分阶段

以每一只耐造的鼹鼠为一个阶段，表示在这只鼹鼠前面（包括这只鼹鼠）可以打到的鼹鼠的数量

2. 确定状态和状态变量

这里使用两个数组 \(f,\ a\) ，分别存储状态和输入的数据

3. 确定决策和状态转移公式

因为每一只鼹鼠都可以和他前面的任何一只鼹鼠结合，所以我们只需要知道究竟是与前面的结合好还是自己好即可，这一点很与最长不下降子序列（LIS） 完全相同，所以公式可以完全照搬： \[ \begin{array}{lr} (0\ <\ j\ ≤\ n)\\ f_i = \max(f_i,\ f_j + 1) \end{array} \]

4. 边界条件

因为每一只鼹鼠都有可能是第一只鼹鼠而且第一只鼹鼠的初始值，也就是我们的边界条件一定是 \(1\) 。所以我们的边界条件就是每一项都是一： \[ f_{1\to n}=1 \]

5. 实现

前面的思路都整理清楚了，实现就非常简单了，基本就是最长不下降子序列改一下，注意：题目要我们求的不是抓的鼹鼠，而是幸存的鼹鼠，所以输出的时候要输出 \(n-ans\ (ans为计算出来的被抓的鼹鼠数量)\) ，代码如下：

#include <iostream>
#include <cmath>

using namespace std;

int n, m, ans, t[10009], x[10009], y[10009], f[10009];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t[i] >> x[i] >> y[i];
        f[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j < i; j++) {
            if (abs(x[i] - x[j]) + abs(y[i] - y[j]) <= abs(t[i] - t[j])) {
                f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
        }
    }
    cout << ans;
}