题解 P2196 【挖地雷】

· · 题解

蒟蒻来发题解了~

由于正解是DP，那我们就用DP

（尽管数据很水可以搜索）

老样子，DP考虑3件事：数组、方程、初始化

一.数组

通过对线性动规的学习我们知道

这类题目的数组大多都是一个一维数组

这题作为典型题目之一，自然逃不出一维数组的手掌心

我们用dp_{i}表示挖地雷时以点i为终点所能挖到的最大地雷数

用a_{i}表示第i个点的地雷数

然后用顺推的方式从2一直推到n

最后输出dp数组存储的最大值即可

二.方程

我们可以借鉴一下最长XX子序列的思路：

for(int i=2;i<=n;++i){
        dp[i]=0;
        for(int j=i-1;j>0;--j){
            if(a[i]>a[j]){
                dp[i]=max1(dp[i],dp[j]);
            }
        }
        dp[i]++;
        if(dp[i]>ans) ans=dp[i];
    }

对于dp_{i}，用j从1到i-1枚举

如果从j到i有路可走且dp_{j}>dp_{i}

那就把dp_{i}的值更新为dp_{j}

枚举结束后把dp_{i}的值加上第i个点的地雷数

一句话，找出点j使得j<i，dp_{j}为最大值且i,j之间有通路

再加上第i个点的地雷数

状态转移方程：

------------ ## 三.初始化 首先，$dp_{1}$=$a_{1}

其次，对于dp_{i}（2<=i<=n），有两种选择：

一是都初始化为0

二是都初始化为a_{i}

前者需在枚举完之后加上a{i}，但判断条件较为简略

后者不需再加上a_{i}，但判断条件略显繁琐

笔者在此选后者

代码来了~||ヽ(￣▽￣)ノミ|Ю

#include<iostream>
#include<cstdio>
#define maxn 201//数组开大一点
#define fo(x) for(register int i=1;i<=x;++i)//宏定义，省事
using namespace std;
bool rd[maxn][maxn];
//rd[i][j]记录i到j是否是通路
//dp[i]表示以i为终点所能挖到的最大地雷数 
//a[i]表示第i个点的地雷数
int a[maxn],dp[maxn],p[maxn],pos;//p[i]表示i的前趋 
void DFS(int x){//倒着输出
    if(p[x]) DFS(p[x]);//如果x有前趋，继续搜
    cout<<x<<" ";
}
int main(){
    int n,ans=0;
    cin>>n;
    fo(n) scanf("%d",&a[i]);
    fo(n-1)
        for(register int j=i+1;j<=n;++j){//按格式输入路径
            scanf("%d",&rd[i][j]);
        }
    dp[1]=a[1];//初始化
    for(register int i=2;i<=n;++i){//从2开始到n结束
        dp[i]=a[i];//初始化
        for(register int j=i-1;j>0;--j){//枚举寻找最大值
            if(rd[j][i]&&dp[i]<dp[j]+a[i]){
            //有路径且大于目前的最大值
                dp[i]=dp[j]+a[i];//更新
                p[i]=j;//记录i的前趋为j
            }
        }
        if(ans<dp[i]){//更新答案
             ans=dp[i];
             pos=i;//记录取点的位置
        }
    }
    DFS(pos);//先输出最优路径
    cout<<endl<<ans;//再输出答案
    return 0;//后话：此题可概括为“最长连通子序列”
}