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 _ptb30_ @ 2024-07-04 14:35:06

@Tjaweiof 因为二维样例没过


上一页 |