文章
2
粉丝
0
获赞
6
访问
301
按拓扑序DP:1、dp二维数组初始化为1,输入点并按照高度升序排序;2、按高度从低到高处理各个点,保存最大值
# include <bits/stdc++.h>
# define ll long long int
using namespace std;
int A[101][101];
struct point{
int x;
int y;
int value;
};
struct cmp{
inline bool operator()(point a, point b) const
{
return a.value < b.value;
}
};
multiset<point, cmp> S;
int main()
{
int m, n;
while(cin>>m>>n)
{
S.clear();
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>A[i][j];
S.insert(point{i, j, A[i][j]});
}
vector<vector<int>> res(m, vector<int>(n, 1));
int maxa = 1;
for(auto it = S.begin(); it!=S.end(); it++)
{
int u = 1, d = 1, l = 1, r = 1;
if(it->x-1 >= 0 && A[it->x-1][it->y] < A[it->x][it->y])
u = res[it->x-1][it->y] + 1;
if(it->x+1 < m && A[it->x+1][it->y] < A[it->x][it->y])
d = res[it->x+1][it-&g...
登录后发布评论
暂无评论,来抢沙发