文章

2

粉丝

0

获赞

6

访问

301

头像
滑雪 题解:
P1568
发布于2026年3月20日 13:55
阅读数 88

按拓扑序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...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发