题目内容

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;
}
最后修改日期:2020年3月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。