洛谷题单指南-动态规划1-P2196 [NOIP1996 提高组] 挖地雷

原题链接：https://www.luogu.com.cn/problem/P2196

题意解读：求一条路径，使得所有点地雷数之和最大。

解题思路：

1、DFS

先建图，再从1~n点分别进行一次DFS，记录过程中地雷总数最大的，并且同时记录遍历的顺序。数据量不大，直接就可以过。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 25;
int n, x, a[N];
vector<int> g[N];
bool flag[N];
int ans;
vector<int> order, ansorder;

void dfs(int u, int sum)
{
    if(sum > ans)
    {
        ans = sum; //更新答案
        ansorder = order; //更新最大答案下的顺序
    }
    flag[u] = true;
    for(int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if(!flag[v])
        {
            flag[v] = true; //标记
            order.push_back(v); //遍历顺序中加入v
            dfs(v, sum + a[v]);
            order.pop_back(); //回溯，遍历顺序中弹出v
            flag[v] = false; //回溯
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            cin >> x;
            if(x == 1) g[i].push_back(j); //领接表建图
        }
    }
    for(int i = 1; i <= n; i++) //从每个点开始dfs
    {
        memset(flag, 0, sizeof(flag)); //重置flag
        order.clear(); //清空保存的遍历顺序
        order.push_back(i); //从i开始
        dfs(i, a[i]);
    }
    for(int v : ansorder) cout << v << " ";
    cout << endl;
    cout << ans;
    return 0;
}

2、DP

比较类似于最长上升子序列

设dp[i]表示以i结束的点的路径采集的最大地雷数

则dp[i] = max(dp[i], dp[j] + a[i])，j是所有到i有路径的点，用g[][]表示图的领接矩阵就是g[j][i] == 1

注意，所有的路径，都是编号小的到编号大的，没有点到1号点有路径

初始化时dp[1] = a[1], a[]保存所有点的地雷数

至于，要输出路径中所有的点，只需要在比较时，把每个点是从哪个点走过来的记录下来，再递归输出，或者借助堆栈输出即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 25;
int n;
int a[N]; //每个点的地雷数
int g[N][N]; //领接矩阵
int dp[N]; //dp[i]表示以i结尾的路径中挖到地雷的最大值
int from[N]; //记录每个点是从哪个点走过来的
int ans, last;

void print(int last)
{
    if(!last) return;
    print(from[last]);
    cout << last << " ";
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            cin >> g[i][j]; //g[i][j]=1表示i->j有边

    dp[1] = a[1];
    for(int i = 2; i <= n; i++)
    {
        dp[i] = a[i];
        for(int j = 1; j < i; j++) //到i点有路径的都是比i小的
        {
            if(g[j][i]) 
            {
                if(dp[j] + a[i] > dp[i])
                {
                    dp[i] = dp[j] + a[i];
                    from[i] = j; //记录i是从j走过来的
                }
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(dp[i] > ans)
        {
            ans = dp[i];
            last = i; //终点
        }
    }

    //print(last); //递归输出
    
    //堆栈输出
    stack<int> order;
    order.push(last);
    while(from[last])
    {
        last = from[last];
        order.push(last);
    }
    while(order.size())
    {
        cout << order.top() << " ";
        order.pop();
    }
    
    cout << endl;
    cout << ans;
    return 0;
}