BlachSnake @ 2021-04-20 20:13:29
#include<algorithm>
#include<stdio.h>
#include<ctype.h>
#define max(x,y) (x<y?x:y)
namespace io{
int Read(){
int x=0;
bool d=0;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')d=1;
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-48;
if(d)x=-x;
return x;
}
void Print(int x){
if(x<0)x=-x,putchar('-');
int a[12],l=0;
for(;x;x/=10)a[l++]=x%10;
if(!l)putchar('0');
for(l--;~l;l--)putchar(a[l]+48);
putchar(' ');
}
}
using namespace io;
using std::sort;
const int N=128,mx[4]={1,0,-1,0},my[4]={0,1,0,-1};
struct node{int x,y,v;}t[N*N];
int a[N][N],f[N][N];
inline bool cmp(node a,node b){return a.v<b.v;}
int main(){
int r=Read(),c=Read(),m=r*c,x,y,s=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
a[i][j]=Read(),t[++s]=(node){i,j,a[i][j]};
sort(t+1,t+m+1,cmp);
s=0;
for(int i=1;i<=m;i++){
x=t[i].x,y=t[i].y;
for(int j=0;j<4;j++)
if(a[x+mx[j]][y+my[j]]<a[x][y])
f[x][y]=max(f[x][y],f[x+mx[i]][y+my[i]]);
f[x][y]++;
s=max(s,f[x][y]);
}
Print(s);
return 0;
}
RT,不知道sort的时候出什么问题了,总是RE……
所以那个WA是什么意思
求调QwQ
by BlachSnake @ 2021-04-20 20:17:56
艹,f[x+mx[i][y+my[i]]
是smg……
还有(x<y?x:y)
又是smg……
已AC,此帖终结
by qqqqq111 @ 2021-04-20 20:35:21
dp这么难的吗连你也。。。
by qqqqq111 @ 2021-04-20 20:47:50
快删吧
by BlachSnake @ 2021-04-21 19:15:01
@qqqqq111 记搜=DP
但DP!=记搜
by qqqqq111 @ 2021-04-21 22:34:35
by tomato1 @ 2021-04-24 11:14:22
DP???