挖地雷动态规划

2021-03-18

题目描述

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

输入格式

有若干行。

第1行只有一个数字，表示地窖的个数N。

第2行有$N$个数，分别表示每个地窖中的地雷个数。

第3行至第$N+1$行表示地窖之间的连接情况：

第3行有$n-1$个数（00或11），表示第一个地窖至第2个、第3个、…、第n个地窖有否路径连接。如第3行为1 1 0 0 0 … 0，则表示第1个地窖至第2个地窖有路径，至第3个地窖有路径，至第4个地窖、第5个、…、第n个地窖没有路径。

第4行有n-2个数，表示第二个地窖至第3个、第4个、…、第n个地窖有否路径连接。

… …

第n+1行有1个数，表示第$n-1$个地窖至第n个地窖有否路径连接。（为0表示没有路径，为1表示有路径）。

输出格式

有两行

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例

输入 #1复制

输出 #1复制

1 2	1 3 4 5 27

说明/提示

【题目来源】

NOIP 1996 提高组第三题

自顶向下的动态规划

import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            val[i] = sc.nextInt();
        }

        int road[][] = new int[n][];
        for (int i = 0; i < n - 1; i++) {
            road[i] = new int[n - i - 1];
            for (int j = 0; j < n - i - 1; j++) {
                road[i][j] = sc.nextInt();
            }
        }

        mem = new int[n];
        next = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(dfs(val, road, i), max);
        }

        int ans = 0, start = 0;
        for (int i = 0; i < n; i++) {
            if (mem[i] > ans) {
                ans = mem[i];
                start = i;
            }
        }
        // 回放动态规划的过程
        Deque<Integer> stack = new LinkedList<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int nextIndex = stack.pop();
            System.out.print((nextIndex + 1) + " ");
            if (next[nextIndex] != 0) stack.push(next[nextIndex]);
        }
        System.out.println();
        System.out.println(max);
    }
	
	// 动态规划表格
    static int[] mem;
    // 记录当前位置的下一个位置，用来回放动态规划的过程
    static int[] next;

    public static int dfs(int[] val, int[][] road, int index) {
        if (index > road.length - 1) return 0;

        if (mem[index] != 0) return mem[index];
        if (index == road.length - 1) {
            mem[index] = val[index];
            return val[index];
        }

        int n = road[index].length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (road[index][i] != 0) {
                int temp = res;
                res = Math.max(res, dfs(val, road, index + i + 1));
                // 记录回放的过程
                if (res != temp) next[index] = index + i + 1;
            }
        }
        mem[index] = res + val[index];
        return res + val[index];
    }
}

自底向上的动态规划

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int dp[MAXN];
int a[MAXN];
int pre[MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        dp[i]=a[i];
    }
    for(int i=1; i<=n-1; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            int b;
            cin>>b;
            if(b)
                if(dp[j]<dp[i]+a[j])
                {
                    dp[j]=dp[i]+a[j];
                    pre[j]=i;
                }
        }
    }
    int ans=0,start=0;
    for(int i=1; i<=n; i++)
    {
        if(ans<dp[i])
        {
            start=i;
            ans=dp[i];
        }
    }
    stack<int> stk;
    stk.push(start);
    while(pre[start])
    {
        stk.push(pre[start]);
        start=pre[start];
    }
    while(stk.size())
    {
        cout<<stk.top()<<' ';
        stk.pop();
    }
    cout<<endl<<ans;
}