网址如下： P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 早上看二进制下标树看到一半被高中同学要求看看这一题 他只说看看，也没问什么东西，怪 就做了一下 思路还算是简单的 dp值代表在这个地窖的最大炸弹数（虽然说起点随便，但是路径是向后的）（虽然我dp的名字用的是bomb） path的值表示从这个地窖通

1996年分区联赛提高组之三 挖地雷 Time Limit:1000MS  Memory Limit:65536K Total Submit:197 Accepted:87 Description 　　在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。  　　例如：  <

[NOIP1996 提高组] 挖地雷 题目描述 在一个地图上有 N ( N ≤ 20 ) N\ (N \le 20) N (N≤20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。 输入格

题目描述】 在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向在序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。 【输入】 第一行：

题目选自洛谷P2196 本题是一道基础的练习题，可以采用动态规划和DFS的方法来求解。 动态规划的解题思路：   DFS的解题思路： 由于只能从数字小的到数字比它大的地方走，所以for i从出发点+1开始，如果有路且没走过就走，更新一下总数。 当总数比之前某一次的值大，我们就更新一下路径和总数。 用a[21]来记录最终的结果，用b[21]来保存每种dfs的路径，更新路径就是把b数组赋给b数组