题解 P2196 【挖地雷】

maorui_cow · 2018-08-08 13:50:43 · 题解

可以说是一道很经典的dp了，还是很简单的

我们可以推出状态转移方针为f[i]=max(a[i]+w[j])

#include<bits/stdc++.h>
using namespace std;
int a[25],s[25][25],t[25],c[25],f[25];
int main()
{
    int n,maxx=0,l,k;
    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",&s[i][j]);//直接记录连接情况
        }
    }
    f[n]=a[n];//这里是从n往下的一个递推
    for(int i=n-1; i>=1; i--)
    {
        l=0,k=0;//注意要清零
        for(int j=i+1; j<=n; j++)
        {
            if(s[i][j]==1&&f[j]>l)//记录最大值
            {
                l=f[j];
                k=j;
            }
        }
        f[i]=l+a[i];//加上地雷数
        c[i]=k;//记录最优顺序
    }
    k=1;
    for(int i=2;i<=n;i++)//计算最多地雷数
    {
        if(f[i]>f[k])
        {
            k=i;
        }
    }
    maxx=f[k];//记下最大值
    cout<<k;
    k=c[k];
    while(k!=0)
    {
        printf(" %d",k);
        k=c[k];
    }
    printf("\n");
    printf("%d\n",maxx);
    return 0;
}

//^w^