解题报告 P2196 挖地雷【NOIP1996TGT3】

题目内容

P2196

大意：在一个地图上有 N 个地窖 (N \le 20)，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。注意是单向边

解题思路

和租船的思路差不多，都是 dp，但关键在于记录路径，所以这里选择倒着 dp，顺着打印路径

f_i=\max\lbrace f_j+a_i\rbrace

表示很讨厌远古的 noip 题，题面各种描述不清

#include <cstdio>

const int maxn=21;
int n,a[maxn],f[maxn],nxt[maxn];
bool b[maxn][maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            scanf("%d",&b[i][j]);
    f[n]=a[n];
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
            if(f[j]>f[i] && b[i][j])
            {
                f[i]=f[j];
                nxt[i]=j;
            }
        f[i]+=a[i];
    }
    int ans=0,st;
    for(int i=1;i<=n;i++)
        if(f[i]>ans)
            ans=f[i],st=i;
    printf("%d ",st);
    for(int i=st;nxt[i];i=nxt[i])
        printf("%d ",nxt[i]);
    printf("\n%d\n",ans);
    return 0;
}