P2196 找地雷

P2196 找地雷

原题链接
题目范围

• \(1 \le n \le 20\)
  

解题思路


ni\}\]
如果从 i 可以走到 j，那就可以先拿第 i 个点的地雷，再接上从 j 开始的最优结果。
因为转移只会用到后面的点，也就是 j > i，所以 dp 要从后往前算。
全部算完后，再找最大的 dp，这个 i 就是最优路径的起点，然后顺着 nxt 一直输出即可。
复杂度分析

• 时间复杂度：\(O(n^2)\)
  
• 空间复杂度：\(O(n^2)\)
  

本题 n 不大，DFS 和 DP 都能过。这里主要开销就是状态转移和存图。
代码实现

[code]#define rep(i,a,b) for(int i=(int)a;i>n;    //初始化    rep(i,1,n+1)cin>>a;    rep(i,1,n)rep(j,i+1,n+1)cin>>f[j];    // 从后往前dp    for(int i=n;i>=1;--i){        dp=a;        for(int j=i+1;j

感谢发布原创作品，程序园因你更精彩

感谢发布原创作品，程序园因你更精彩