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 <bits/stdc++.h>
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 <= n; i++) cin >> val[i];
    for(int i = 1; i <= n; i++) dp[i] = val[i];
    for(int i = 1; i <= n - 1; i++){
        for(int j = i + 1; j <= n; j++) cin >> g[i][j];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(g[j][i] && dp[j] + val[i] > dp[i]){
                dp[i] = dp[j] + val[i];
                q[i] = j;
            }
        }
    }
    int x = 0, tot = 0;
    for(int i = 1; i <= n; i++) if(dp[x] < dp[i]) x = i;
    ans = dp[x];
    while(x){
        fro[++tot] = x;
        x = q[x];
    }
    for(int i = tot; i >= 1; i--) cout << fro[i] << ' ';
    cout << endl;
    cout << ans << endl;
    return 0;
}