洛谷P2196 [NOIP1996 提高组] 挖地雷【动态规划思路分析】看完直接举一反三！
P2196 [NOIP1996 提高组] 挖地雷
前言
我发现我是天才，只做了三道动态规划的类型题就感觉我已经炉火纯青了。大家快来看看我是怎么做的！思路很重要啊！
题目
题目描述
在一个地图上有
N
(
N
≤
20
)
N (N le 20)
N (N≤20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
输入格式
有若干行。
第
1
1
1 行只有一个数字，表示地窖的个数
N
N
N。
第
2
2
2 行有
N
N
N 个数，分别表示每个地窖中的地雷个数。
第
3
3
3 行至第
N
+
1
N+1
N+1 行表示地窖之间的连接情况：
第
3
3
3 行有
n
−
1
n-1
n−1 个数（
0
0
0 或
1
1
1），表示第一个地窖至第
2
2
2 个、第
3
3
3 个、…、第
n
n
n 个地窖有否路径连接。如第
3
3
3 行为
11000
⋯
0
11000cdots 0
11000⋯0，则表示第
1
1
1 个地窖至第
2
2
2 个地窖有路径，至第
3
3
3 个地窖有路径，至第
4
4
4 个地窖、第
5
5
5 个、…、第
n
n
n 个地窖没有路径。
第
4
4
4 行有
n
−
2
n-2
n−2 个数，表示第二个地窖至第
3
3
3 个、第
4
4
4 个、…、第
n
n
n 个地窖有否路径连接。
……
第
n
+
1
n+1
n+1 行有
1
1
1 个数，表示第
n
−
1
n-1
n−1 个地窖至第
n
n
n 个地窖有否路径连接。（为
0
0
0 表示没有路径，为
1
1
1 表示有路径）。
输出格式
第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。
第二行只有一个数，表示能挖到的最多地雷数。
样例 #1
样例输入 #1
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
样例输出 #1
1 3 4 5
27
题目分析
对于一点动态规划觉悟都没有的我来说，这道题一看就不像是动态规划的题，至少没有那么明显。我更想使用暴力搜索来做，毕竟N
≤
le
≤ 20很让人心动，但是考虑不包含技术性还是算了（小伙伴可以自己尝试一下）。
接着就来考虑状态转移方程，让我们来看在哪里我们的数据会发生变化。很显然，在换到另一个地窖里的时候，而数值是每个地窖的地雷数，所以我们想，如果每次换地窖的时候都可以知道以后地窖的最大地雷数不就好了，所以我们把状态转移方程的重心落在相邻地窖的数量关系上。
我要进入一个地窖，我肯定是想进入更好的，地雷数最多的地窖，所以我们就有下列方程
f(i)=max[ f(可行) ]+num[i]
所以我们希望可以找到一个开始或者制定一个规则，使得方程不会陷入死循环，或者说要让它无后效性(先进行的计算不会影响后面的结果)。
为了保证无后效性，我们需要从最后面的地窖开始算起，因为这个地窖只能由浅入深，所以先处理后面的地窖。并且将最优的下一个地窖存入path里。
最后就遍历一遍f[]，找到最大的ans并通过存储的path一个一个将路径输出。
注意事项
1.地窖只能深入，不是图！所以1–>5不能通过1–>3–>5来实现，这也是能从更深层的地窖开始建立动态规划方程的前提。（一开始我也以为是图，结果想了好久）
2.f中最后一个地窖单独处理，不算入方程中，就像高中的数列总是有一个初始的a0一样。
3.注意路径后面的输出要补一个now，否则没有完全输出完
4.最后一个地窖是不能到任何其他地窖的，所以它的值应该是0，所以在这一步终止。等于0的情况也可能是其他地窖不能到其他地窖（比如例题的地窖3）。但是可以肯定的是路径的最后一步的path[now]一定为0，否则可以前往任意一个可以前往的地窖，从而获得更大的地雷数
代码
#include<iostream>
using namespace std;
int a[1007][1007]={0},num[27]={0},path[27]={0},f[27]={0};
int main(){
int n,maxx=0,ans=0,now=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
cin>>a[i][j];
}
}
f[n]=num[n];
for(int i=n-1;i>0;i--){
maxx=0;//maxx需要更新
for(int j=i+1;j<=n;j++){//获得可行域最大值
if(a[i][j])
if(f[j]>f[maxx])
maxx=j;
}
path[i]=maxx;//记录路径
f[i]=f[maxx]+num[i];//动态规划方程
}
//找到f[]中的最大值
for(int i=1;i<=n;i++){
if(f[i]>f[ans])
ans=i;
}
now=ans;
while(path[now]){//等于0说明结束了，末尾没有其他路径了
cout<<now<<" ";
now=path[now];
}
cout<<now<<endl;
cout<<f[ans]<<endl;
return 0;
}
后话
额外测试用例
因为忘记输出路径而获得了一个用例
样例输入 #2
3
10 20 5
0 1
0
样例输出 #2
2
20
王婆卖瓜
感觉有收获或者想跟上我的进度刷题的，可以点个关注，或者点赞收藏评论都可以！
题目来源
NOIP 1996 提高组第三题
洛谷链接