gosgosgoy @ 2020-09-19 19:49:30
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int n;
int m;
int h;
};
node t[10005];
int c,r,ans;
bool cmp(node x,node y){
return x.h<y.h ;
}
int a[105][105];
int dp[105][105];
int main(){
scanf("%d %d",&c,&r);
for(register int i=0;i<=c+1;i++)
for(register int j=0;j<=r+1;j++)
a[i][j]=-1;
for(int i=0;i<c;i++)
for(int j=0;j<r;j++){
scanf("%d",&a[i+1][j+1]);
t[i*c+j].h=a[i+1][j+1];
t[i*c+j].n=i+1;
t[i*c+j].m=j+1;
}
sort(t,t+c*r,cmp);
int p,q;
//for(register int i=0;i<c;i++)
// for(register int j=0;j<r;j++){
// p=t[i*c+j].n;
// q=t[i*c+j].m;
for(register int i=0;i<r*c;i++){
p=t[i].n;
q=t[i].m;
dp[p][q]=1;
if((a[p+1][q]>-1)&&a[p+1][q]<a[p][q]){
dp[p][q]=max(dp[p][q],dp[p+1][q]+1);
}
if((a[p-1][q]>-1)&&a[p-1][q]<a[p][q]){
dp[p][q]=max(dp[p][q],dp[p-1][q]+1);
}
if((a[p][q+1]>-1)&&a[p][q+1]<a[p][q]){
dp[p][q]=max(dp[p][q],dp[p][q+1]+1);
}
if((a[p][q-1]>-1)&&a[p][q-1]<a[p][q]){
dp[p][q]=max(dp[p][q],dp[p][q-1]+1);
}
// ans=max(dp[p][q],ans);
}
for(int i=1;i<=c;i++)
for(int j=1;j<=r;j++)
ans=max(dp[i][j],ans);
printf("%d\n",ans);
}
by sunxiaohan @ 2020-09-19 19:53:22
搜索不好吗?
by gosgosgoy @ 2020-09-19 20:10:06
@sunxiaohan 正在练DP专题,搜索确实好过这题
by sunxiaohan @ 2020-09-19 20:26:06
这不是道DP好题吧
by sunxiaohan @ 2020-09-19 20:26:21
@gosgosgoy