求最长下降子序列
记忆化搜索，每次求以(i,j)为起点的最长下降子序列，并且记录下来。然后遍历dp。
#include<iostream> using namespace std; #define N 105 int map[N][N],dp[N][N]; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; int row,col; int dfs(int r,int c) { if(dp[r][c]>0) return dp[r][c]; int i,nmax=1,len,rr,cc; for(i=0;i<4;i++) { rr=r+dir[i][0]; cc=c+dir[i][1]; if(rr<1||rr>row||cc<1||cc>col) continue; if(map[r][c]>map[rr][cc]) { len=dfs(rr,cc)+1; if(nmax<len) nmax=len; } } return nmax; } int main() { int i,j; scanf("%d%d",&row,&col); for(i=1;i<=row;i++) for(j=1;j<=col;j++) scanf("%d",&map[i][j]); memset(dp,0,sizeof(dp)); for(i=1;i<=row;i++) for(j=1;j<=col;j++) dp[i][j]=dfs(i,j); int nmax=0; for(i=1;i<=row;i++) for(j=1;j<=col;j++) if(dp[i][j]>nmax) nmax=dp[i][j]; printf("%d/n",nmax); return 0; }
