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 都能过。这里主要开销就是状态转移和存图。
代码实现
#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; // 从后往前dp for(int i=n;i>=1;--i){ dp=a; for(int j=i+1;j 感谢发布原创作品，程序园因你更精彩 感谢发布原创作品，程序园因你更精彩
页:
[1]