一本通-1262：【例9.6】挖地雷（基础动态规划）

【题目描述】 在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向在序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

【输入】 第一行：地窖的个数；

第二行为依次每个地窖地雷的个数；

下面若干行：

xi yi //表示从xi可到yi，xi<yi。

最后一行为"0 0"表示结束。

【输出】 k1−k2−…−kv //挖地雷的顺序 挖到最多的雷。

【输入样例】 6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0

【输出样例】 3-4-5-6 34

---

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int> > grid(205, vector<int>(205));
vector<int> d(205);
vector<int> weight(205);
vector<int> nextPos(205);

void solve()
{
    d[n] = weight[n];
    for (int i = n - 1; i >= 1; --i) {
        for (int j = i + 1; j <= n; ++j) {
            if (grid[i][j] && d[i] < weight[i] + d[j]) {
                d[i] = weight[i] + d[j];
                nextPos[i] = j;
            }
        }
    }

    int pos = 0;
    int maxNum = INT_MIN;
    for (int i = 1; i <= n; ++i) {
        if (d[i] > maxNum) {
            maxNum = d[i];
            pos = i;
        }
    }

    while (pos) {
        cout << pos;
        pos = nextPos[pos];
        if (pos != 0) cout << '-';
    }
    cout << endl;
    cout << maxNum << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> weight[i];
        d[i] = weight[i];
    }

    int from, to;
    while ((cin >> from >> to) && (from != 0 || to != 0)) {
        grid[from][to] = 1;
    }
    solve();

    return 0;
}

这道题目最初在51行的初始化部分漏掉了造成错误。

思路和城市路线那道题差不多。因为路线是单向的，并且是从小序号指向大序号，那么完全可以从大序号逆推。

用d[i]代表从i开始所能挖到的最大地雷。状态转移方程： $$ d[i] = \max (weight[i] + d[j]), \quad grid[i][j] = 1 $$