_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 你告诉我你的
by _ptb30_ @ 2024-07-04 14:23:17
@Tjaweiof 到编号为i的点的最长路径是多长
by Tjaweiof @ 2024-07-04 14:26:03
@ptb30 注意你的第
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