题解与反思

P2196 [NOIP1996 提高组] 挖地雷

思路

  1. 图的DP问题，就是找一条最大的价值最大的路径。

  2. 经过某个点的价值可以由以上一个点为结尾的路径推导过来，所以我们考虑用DP。

  3. （1）状态表示：f[i] 表示以i点结尾的路径的价值的集合，属性值：最大值

    （2）状态转移：我们以第i个点前驱结点进行划分， f[i] = max(f[j] + a[i], f[i]),其中j为i的前驱结点。

  4. 题目要求记录路径，所以我们用pre[i] 存储i的前驱结点。

  5. 在更新f[i]的过程中记录，最大值和最大路径的结尾ed，通过dfs，pre[ed]，输出最佳路径。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int g[N][N];
int a[N], pre[N];
int f[N];//表示以第i个点结尾的路径的最大地雷数
void dfs(int ed)
{
    if(pre[ed] != 0) dfs(pre[ed]);
    cout << ed << " ";
}
int main()
{
    int n;
    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 ++)
        {
            int x;
            cin >> x;
            g[i][j] = x;
        }
    }
    int res = -1e9, ed = -1;
    for(int i = 1; i <= n; i ++)
    {
        f[i] = a[i];
        for(int j = 1; j <= n; j ++)
        {
            if(g[j][i] == 1 && f[i] < f[j] + a[i])
            {
                f[i] = f[j] + a[i];
                pre[i] = j;
            }
        }
        if(f[i] > res)
        {
            res = f[i];
            ed = i;
        }
    }
    dfs(ed);//输出路径
    cout << endl;
    cout << res << endl;
    return 0;
}

P1802 5 倍经验日

思路

  1. 01背包的变形问题，但是注意的点非常多。

  2. 先分析一下题意，刚开始题意没弄明白，直接全WA。每个对手我们可以选择打败或者不打败（在药满足条件的情况下），并且我们可以不用药，直接选择失败，这样既能获得失败的经验值，还没有消耗药，肯定是最优解。

  3. 所以在考虑每个对手的时候就是两种状态，成功或失败。

  4. （1）状态表示：f[i][j] 表示考虑前i个对手，用j瓶药获得的经验值的集合，属性值：最大值

    （2）状态划分：我们以第i个对手成功或者失败进行划分。

  5. 状态转移的f[i - 1][j] 怎么理解，我们枚举的当前的药为j个，并且当前的i对手用了0个药，所以i-1层应该用了j-0个药

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
typedef long long LL;
int f[N][N];
int lose[N], win[N], use[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> lose[i] >> win[i] >> use[i];
    }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j <= m; j ++)
        {
           //当前的药大于战胜i对手的药时，我们可以选择成功或者在用0个药的前提下失败
           //当前的药小于战胜i对手的药时，我们直接选择用0个药的代价失败，直接累加经验值
            if(j >= use[i])
            {
                f[i][j] = max({f[i][j], f[i - 1][j - use[i]] + win[i], f[i - 1][j] + lose[i] });
            }
            else f[i][j] = f[i - 1][j] + lose[i];
        }
    }
    cout << (LL)f[n][m] * 5 << endl;
    return 0;
}

P1434 [SHOI2002] 滑雪

思路

  1. 参考大佬的思路
  2. 把每个点存为一个元素，则它的最长路径来自它的上下左右四边的最长的最长路+1。
  3. 但是dp要考虑无后效性。这就是为什么要用priority_queue，先算较低的点，用较低的山更新较高的山。最后遍历一遍整个地图，求出最高的一个点。
  4. 我们用小根堆，每次用最矮的山更新可达的较高的山。
  5. 注意小根堆的< 重载应该是从大到小排序。
#include<iostream>
#include<queue>
using namespace std;
const int N = 1005;
int dx[] = {1,-1, 0, 0};
int dy[] = {0, 0, 1,-1};
struct node
{
    int x, y, w;
    bool operator < (const node & t) const
    {
        return w > t.w;//从大到小排序，queue变成小根堆
    }
} p[N * N];
int h[N][N];
int f[N][N];//表示从（i，j）开始滑的最长路径
priority_queue<node> pp;
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> h[i][j];
            p[i].w = h[i][j];
            p[i].x = i;
            p[i].y = j;
            pp.push(p[i]);
        }
    }
    //初始化
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++) f[i][j] = 1;
    }
    int res = -1e9;
    while(!pp.empty())
    {
        int xx = pp.top().x;
        int yy = pp.top().y;
        int ww = pp.top().w;
        pp.pop();
        for(int i = 0; i < 4 ; i ++)
        {
            int rx = dx[i] + xx;
            int ry = dy[i] + yy;
            if(rx < 0 || ry < 0 || rx > n || ry > n) continue;
            if(h[rx][ry] < ww)
            {
                f[xx][yy] = max(f[xx][yy], f[rx][ry] + 1);
            }
             res = max(res, f[xx][yy]);
        }
    }
    cout << res << endl;
    return 0;
}