20分dp,萌新求助qwq
查看原帖
20分dp,萌新求助qwq
791626
Parsifa1楼主2022/9/28 15:56
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int l[101][101],dp[101][101];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},k;

struct node {
int num;
int x,y;
}a[10001];

int read() {          //偷的快读(
	int x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

bool cmp(node x,node y){
	return x.num<
    y.num;
}

int main() {
    int r,c,ans=0;
    r=read();
    c=read();
    
    for(int i=0;i<r;i++) {      //读入并储存到一维数组中以便排序
        for(int j=0;j<c;j++) {
            l[i][j]=read();
            a[k++].num=l[i][j];
            a[k].x=i;a[k].y=j;
        }
        
    }

    sort(a,a+k,cmp);
   
    for(int i=0;i<k;i++) {
        int x0=a[i].x,y0=a[i].y;
        for(int j=0;j<4;j++) {
            int x1=a[i].x+dx[j],y1=a[i].y+dx[j];
            if(x0>=0&&x0<r&&y0>=0&&y0<c) {
                if(l[x0][y0]<l[x1][y1]) {
                    dp[x0][y0]=max(dp[x1][y1]+1,dp[x0][x0]);                   
                }
            } 
        }
        ans = max(dp[x0][y0],ans);
    }
    cout<<ans+1;
}
2022/9/28 15:56
加载中...