P2196 [NOIP1996 提高组] 挖地雷 线性动态规划DP 题解

原题链接：[P2196 NOIP1996 提高组] 挖地雷 - 洛谷)

题目分析

看到这道题，首先感觉是个搜索，如果数据范围不大应该没问题。但是，，，我没找到数据范围啊喂~

那就动态规划一下，先用二维数组存一下联通性，然后用 d p [ i ] dp[i] dp[i]表示以第 i i i个地窖结尾的最大值，则不难推出状态转移方程：
d p [ i ] = m a x ( d p [ j ] + v a l [ i ] , d p [ i ] ) dp[i] = max(dp[j] + val[i], dp[i]) dp[i]=max(dp[j]+val[i],dp[i])
此外，由于要输出路径，因此需要额外记录前驱，前驱可以递归输出，也可以打循环转制输出。

AC Code

#include 
using namespace std;
const int N = 30;
int val[N], g[N][N], dp[N], q[N], fro[N];
int ans = 0;


int main(){
    int n = 0; cin >> n;
    for(int i = 1; i > val[i];
    for(int i = 1; i