徐至 @ 2018-07-25 19:29:50
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int R,C,num;
const int maxn=107;
const int maxm=1e5+7;
int ind[maxn*maxn];
int f[maxn][maxn],hh[maxn][maxn];
struct Node{
int x,y,h;
}node[maxn];
int dp[maxn];
struct Edge{
int next,to;
}edge[maxm];
int head[maxn*maxn];
priority_queue<int>q;
void add(Node a,Node b){
int aa=(a.x-1)*C+a.y;
int bb=(b.x-1)*C+b.y;
edge[++num].next=head[aa];
edge[num].to=bb;
head[aa]=num;
}
void process(){
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++){
if(node[(i-1)*C+j].h>node[(i-2)*C+j].h) {add(node[(i-1)*C+j],node[(i-2)*C+j]);ind[(i-2)*C+j]++;}
if(node[(i-1)*C+j].h>node[(i-1)*C+j-1].h) {add(node[(i-1)*C+j],node[(i-1)*C+j-1]);ind[(i-1)*C+j-1]++;}
if(node[(i-1)*C+j].h>node[(i-1)*C+j+1].h) {add(node[(i-1)*C+j],node[(i-1)*C+j+1]);ind[(i-1)*C+j+1]++;}
if(node[(i-1)*C+j].h>node[i*C+j].h) {add(node[(i-1)*C+j],node[i*C+j]);ind[i*C+j]++;}
}
for(int i = 1;i <= C*R;i++){
if(ind[i] == 0) {q.push((node[i].x-1)*C+node[i].y);f[node[i].x][node[i].y]=1;}//不能存Node
}
num = 0;
while(!q.empty()){
int aa = q.top();q.pop();dp[++num] = aa;
for(int i = head[aa];i;i = edge[i].next){
int v = edge[i].to;
ind[v]--;
if(ind[v] == 0) {
q.push(v);
}
}
}
}
int main(){
cin>>R>>C;
for(int i=1;i<=R;i++){
for(int j=1;j<=C;j++){
int hg;cin>>hg;
node[++num].x=i;
node[num].y=j;
node[num].h=hg;
hh[i][j]=hg;
}
}
num = 0;
process();
for(int i = 1;i <= num;i++){
int xx,yy;
if(dp[i]%C != 0) {xx=dp[i]/C+1;yy=dp[i]-(C*(xx-1));}
if(dp[i]%C == 0) {xx=dp[i]/C;yy=C;}
if(hh[xx][yy]>hh[xx-1][yy]) f[xx-1][yy]=max(f[xx][yy]+1,f[xx-1][yy]);
if(hh[xx][yy]>hh[xx+1][yy]) f[xx+1][yy]=max(f[xx][yy]+1,f[xx+1][yy]);
if(hh[xx][yy]>hh[xx][yy-1]) f[xx][yy-1]=max(f[xx][yy]+1,f[xx][yy-1]);
if(hh[xx][yy]>hh[xx][yy+1]) f[xx][yy+1]=max(f[xx][yy]+1,f[xx][yy+1]);
}
int ans=0;
for(int i=1;i<=R;i++){
for(int j=1;j<=C;j++){
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
return 0;
}
by andyli @ 2018-07-25 20:32:48
@徐至
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 105;
const int dir[][2] =
{
{1, 0},{0, 1},{-1, 0},{0, -1}
};
int r, c, A[maxn][maxn], vis[maxn][maxn];
int dfs(int i, int j)
{
if (vis[i][j] != 1)
return vis[i][j];
int ans = 0;
for (int k = 0; k < 4; k++)
{
int newi = i + dir[k][0], newj = j + dir[k][1];
if (newi >= 0 && newj >= 0 && newi < r && newj < c && A[i][j] > A[newi][newj])
ans = max(ans, dfs(newi, newj) + 1);
}
return vis[i][j] = max(vis[i][j], ans);
}
int main()
{
cin >> r >> c;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> A[i][j], vis[i][j] = 1;
int ans = -1;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
ans = max(ans, dfs(i, j));
cout << ans << endl;
return 0;
}by 徐至 @ 2018-07-26 19:23:05
谢谢，不过我还是不懂为啥RE了？