iphxer
思路： 看着 分类为dp。 本着不熟的dp思想，硬是编了个像dp的东西。。 没想到还是超时，，，，（写的很复杂，想着都不会过。。）
结果就换了个 dfs 看能不能成，，一下就ac了。。。。0.0
我的 dp 错误代码
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #include<queue> #define inf 0x3f3f3f #define M 100+10 using namespace std; int map[M][M]; int dp[M][M]; int to[4][2]={1,0,-1,0,0,1,0,-1}; int main() { int n; scanf("%d",&n); while(n--) { int row,lie; scanf("%d%d",&row,&lie); memset(map,0,sizeof(map)); for(int i=1;i<=row;i++) { for(int j=1;j<=lie;j++) { scanf("%d",&map[i][j]); dp[i][j]=1; } } int max=0; for(int u=1;u<500;u++) // 这个u要很大才可以，，就是要dp遍历好几遍才可以得到最大的 { for(int i=1;i<=row;i++)//dp { for(int j=1;j<=lie;j++) { for(int k=0;k<4;k++) { int ni=i+to[k][0]; int nj=j+to[k][1]; if(map[i][j]<map[ni][nj]&&dp[i][j]<dp[ni][nj]+1) { dp[i][j]=dp[ni][nj]+1; if(max<dp[i][j]) max=dp[i][j]; } } } } } printf("%d\n",max); } return 0; }
dfs ac代码
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #include<queue> #define inf 0x3f3f3f #define M 100+10 using namespace std; int row,lie; int map[M][M]; int num; int to[4][2]={0,1,0,-1,-1,0,1,0}; void dfs(int x,int y,int step) { if(step>num) num=step; // 找出 每一次dfs中最长的路径 for(int k=0;k<4;k++) { int nx=x+to[k][0]; int ny=y+to[k][1]; if(map[nx][ny]&&map[nx][ny]<map[x][y]) { dfs(nx,ny,step+1); } } } int main() { int n; scanf("%d",&n); while(n--) { scanf("%d%d",&row,&lie); memset(map,0,sizeof(map)); for(int i=1;i<=row;i++) { for(int j=1;j<=lie;j++) scanf("%d",&map[i][j]); } int maxx=0;num=0; for(int i=1;i<=row;i++) { for(int j=1;j<=lie;j++) // 由于起点不同，每个dfs的结果不一样，，这个时候再找出 这些中的最大就可以了 { dfs(i,j,0); if(num>maxx) maxx=num; // 获得 所有dfs中的最大值 } } printf("%d\n",maxx+1); } return 0; }
网上找的dp解 （看了之后有点凌乱）
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> using namespace std; const int MAXN = 100+5; int G[MAXN][MAXN][4]; int d[MAXN][MAXN]; int a[MAXN][MAXN]; int max(int a, int b){ if(a>b) return a; else return b; } int dp(int i, int j, int r, int c){ int& ans = d[i][j]; if(ans>0) return ans; ans = 1; if((i-1>=0) && G[i][j][0]) ans = max(ans, dp(i-1, j, r, c)+1); //向上 if((i+1<=r-1) && G[i][j][2]) ans = max(ans, dp(i+1, j, r, c)+1); //向下 if((j-1>=0) && G[i][j][3]) ans = max(ans, dp(i, j-1, r, c)+1); //向左 if((j+1<=c-1) && G[i][j][1]) ans = max(ans, dp(i, j+1, r, c)+1); //向右 return ans; } int _G(int r, int c) { //存图时，每个点数据都已经事先存储好了 for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ if((i-1>=0) && a[i][j]>a[i-1][j]) G[i][j][0] = 1; //向上 if((i+1<=r-1) && a[i][j]>a[i+1][j]) G[i][j][2] = 1; //向下 if((j-1>=0) && a[i][j]>a[i][j-1]) G[i][j][3] = 1; //向左 if((j+1<=c-1) && a[i][j]>a[i][j+1]) G[i][j][1] = 1; //向右 } } } void init(){ memset(G, 0, sizeof(G)); memset(d, 0, sizeof(d)); memset(a, 0, sizeof(a)); } /* void print_map(int r, int c){ //打印存图 for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ printf("(%d,%d,%d,%d) ", G[i][j][0], G[i][j][1], G[i][j][2], G[i][j][3]); //括号中的顺序代表上右下左分别是否能走通 } printf("\n"); } } */ int main(){ int T; scanf("%d", &T); while(T--){ int r, c; scanf("%d%d",&r, &c); init(); for(int i = 0; i < r; i++){//存储点 for(int j = 0; j < c; j++) { scanf("%d", &a[i][j]); } } _G(r,c);//存图 int ans = 0; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++) { ans = max(ans, dp(i, j, r, c)); } } printf("%d\n", ans); // print_map(r, c); } return 0; }