[NOIP1996 提高组] 挖地雷

题目描述

在一个地图上有N个地窖(N≤20)，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。

当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，

然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入描述

地窖个数N

每个地窖的地雷数

地窖之间的连通状态（0为不通，1为通）

输出描述

第一行挖最多地雷的顺序，空格隔开

第二行挖最多地雷的数量

题解

提高组水题

这道题有两个步骤

一、数量

用递推

定义前i个点能挖到的最大数量的地雷为f[i]

则f[i]=max(f[1],f[2],...f[i-1])+a[i]（当然前提是连通）

所以答案就是f数组中的最大值

二、顺序

用hs数组记录哪个结点到i，能让f[i]最大

深搜查找总顺序

三、代码

#include<iostream>

using namespace std;

int n,a[55],sum,f[55],hs[55],ans;

bool map[55][55];

void dfs(int x){

    if(x<=0) return ;

    dfs(hs[x]);

    cout<<x<<" ";

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    for(int i=1;i<n;i++)

        for(int j=i+1;j<=n;j++)

            cin>>map[i][j];

    for(int i=1;i<=n;i++){

        f[i]=a[i];

        for(int j=1;j<i;j++){

            if(map[j][i]&&f[j]+a[i]>f[i]){

                f[i]=f[j]+a[i];

                hs[i]=j;

            }

        }

        if(f[i]>sum){

            sum=f[i];

            ans=i;

        }

    }

    dfs(hs[ans]);

    cout<<ans<<endl;

    cout<<sum;

    return 0;

}

巴特西

[NOIP1996 提高组] 挖地雷

最新文章

热门文章