Amcute @ 2017-06-05 20:52:10
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int pos[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
struct po{
int x;
int y;
int height;
};
bool cmp(po p1,po p2){
return p1.height>p2.height;
}
po p[10010];
int h[101][101];
int s[101][101];
int main() {
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
p[i*m+j].x = i;
p[i*m+j].y = j;
cin>>p[i*m+j].height ;
h[i][j] = p[i*m+j].height ;
s[i][j] = 1;
}
sort(p,p+m*n,cmp);
for(int i = 0; i < m*n;i++)
for(int k = 0; k < 4;k++){
int xx = p[i].x + pos[k][0];
int yy = p[i].y + pos[k][1];
if (xx >= 0 && xx < m&&yy>=0 && yy < n && h[xx][yy] < p[i].height)
s[xx][yy] =max(s[p[i].x][p[i].y]+1,s[xx][yy]);
}
int ma = 1,mi,mj;
cout<<endl<<endl;
for (int i = 0; i < m; i++){
for(int j = 0; j < n; j++)
{ma = max(ma,s[i][j]);
mi = i;
mj = j;
cout<<s[i][j]<<" ";
}
cout<<endl;
}
// cout<<ma<<" "<<mi<<" "<<mj<<endl;
return 0;
}
by Amcute @ 2017-06-05 20:53:18
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int dp[101][101];
int pos[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int ma = 0;
struct po{
int x;
int y;
int height;
};
bool cmp(po p1,po p2){
return p1.height>p2.height;
}
po p[10010];
int h[101][101];
int s[101][101];
int main() {
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
p[i*m+j].x = i;
p[i*m+j].y = j;
cin>>p[i*m+j].height ;
h[i][j] = p[i*m+j].height ;
s[i][j] = 1;
}
sort(p,p+m*n,cmp);
for(int i = 0; i < m*n;i++)
for(int k = 0; k < 4;k++){
int xx = p[i].x + pos[k][0];
int yy = p[i].y + pos[k][1];
// cout<<p[i].x<<" "<<p[i].y<<" ";
// cout<<xx*m+yy<<" "<<p[xx*m+yy].height<<endl;
if (xx >= 0 && xx < m&&yy>=0 && yy < n && h[xx][yy] < h[p[i].x][p[i].y])
s[xx][yy] =max(s[p[i].x][p[i].y]+1,s[xx][yy]);
}
int ma = 1;
for (int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
ma = max(ma,s[i][j]);
cout<<ma<<endl;
return 0;
}