题解 P2196 【挖地雷】

Drawing_Yang · 2018-07-09 21:09:38 · 题解

分析

看各位大佬用的基本上都是逆推的思想,本蒟蒻就发一个顺推的把.其实也不难想.定义状态f[i]为以第i个节点结束的最大值,则f[i]=max \{ f[j]\}+a[i]\ \ (g[j][i]=1),这样就不难写出代码来了.至于输出,用一个pre[i]数组存储i的前驱结点,递归输出即可.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,a[205],g[205][205],pre[205],t,f[205],ans;
void print(int x) {
    if (pre[x]==0) {
        printf("%d",x);
        return;
    }
    print(pre[x]);
    printf(" %d",x); 
}
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++) {
            int x;
            scanf("%d",&x);
            if (x==1) g[i][j]=1;
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            if (g[j][i]&&f[j]>f[i]) {
                f[i]=f[j];
                pre[i]=j;
            }
        }
        f[i]+=a[i];
        if (f[i]>ans) {
            ans=f[i];
            t=i;
        }
    }
    print(t);
    printf("\n%d",ans);
    return 0;
}