dp玄学WA80
查看原帖
dp玄学WA80
319803
CarroT1212楼主2021/6/13 11:20

本人太菜,写个dp还能错,调了挺久还是WA了#1 #2,求调qwq

#include <bits/stdc++.h>
using namespace std;
int n,m,sz[101][101],zg[101][101],maxx;
int xx[4]={-1,0,0,1},yy[4]={0,-1,1,0};
struct node {
	int a,b,c;
}qr[10001];
bool cmp(node &a,node &b) {
	return (a.a<b.a);
}
int main() {
	cin>>n>>m;
	for (int a=0;a<n;a++) {
		for (int b=0;b<m;b++) {
			cin>>sz[a][b];
			qr[a*n+b].a=sz[a][b];
			qr[a*n+b].b=a;
			qr[a*n+b].c=b;
		}
	}
	sort(qr,qr+n*m,cmp);
	for (int a=0;a<n*m;a++) {
		int nx=qr[a].b,ny=qr[a].c;
		zg[nx][ny]=1;
		for (int a=0;a<4;a++) {
			int mx=nx+xx[a],my=ny+yy[a];
			if (zg[mx][my]!=0&&zg[mx][my]>=zg[nx][ny]&&mx>=0&&mx<n&&my>=0&&my<m&&sz[mx][my]<sz[nx][ny]) { //初步判断可能是这里错了
				zg[nx][ny]=zg[mx][my]+1;
			}
		}
		if (zg[nx][ny]>maxx) maxx=zg[nx][ny];
	}
	cout<<maxx;
}
2021/6/13 11:20
加载中...