40pts求助,有一点注释!(玄关)

P1434 [SHOI2002] 滑雪

_ptb30_ @ 2024-07-04 14:15:06

#include <bits/stdc++.h>
#define ll long long
#define N 101
#define inf -10001
using namespace std;

vector<int> edges[N * N];
int R, C;
int a[N][N];
int dp[N];

int main() {
    scanf("%d%d", &R, &C);
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) {
            if (a[i][j] > a[i + 1][j] && i + 1 <= R)//有向边是从编号大的点向编号小的点连
                edges[a[i][j]].push_back(a[i + 1][j]);
            if (a[i][j] > a[i - 1][j] && i - 1 >= 1)
                edges[a[i][j]].push_back(a[i - 1][j]);
            if (a[i][j] > a[i][j + 1] && j + 1 <= C)
                edges[a[i][j]].push_back(a[i][j + 1]);
            if (a[i][j] > a[i][j - 1] && j - 1 >= 1)
                edges[a[i][j]].push_back(a[i][j - 1]);
        }//建一个有向图
    for (int i = 1; i <= R * C; i++)
        dp[i] = inf;
    dp[1] = 1;
    for (int i = 2; i <= R * C; i++) {
        for (auto &j : edges[i])
            dp[i] = max(dp[i], dp[j] + 1);
    }//转移状态
    int ans = 0;
    for (int i = 1; i <= R * C; i++)
        ans = max(dp[i], ans);//求答案
    printf("%d", ans);
}

by Tjaweiof @ 2024-07-04 14:22:02

@ptb30 你告诉我你的 dp_i 是什么


by _ptb30_ @ 2024-07-04 14:23:17

@Tjaweiof 到编号为i的点的最长路径是多长


by Tjaweiof @ 2024-07-04 14:26:03

@ptb30 注意你的第 19 行到第 26


by _ptb30_ @ 2024-07-04 14:26:32

@Tjaweiof okok


by Tjaweiof @ 2024-07-04 14:26:44

你的 edges 存的是高度,但是后来是直接使用 dp[j]


by _ptb30_ @ 2024-07-04 14:29:19

@Tjaweiof 可是我的j用的是auto啊


by Tjaweiof @ 2024-07-04 14:30:35

@ptb30 这我知道


by Tjaweiof @ 2024-07-04 14:30:52

@ptb30 我觉得你的整体思路就不对啊


by Tjaweiof @ 2024-07-04 14:31:14

@ptb30 为什么你的 dp 只开一维。


by _ptb30_ @ 2024-07-04 14:31:53

@Tjaweiof 哦哦哦,我明白了,我的dp[j]其实是0


| 下一页