首页 > 代码库 > nyoj10 滑雪
nyoj10 滑雪
dp[
i][j]=max(四个方向点)+1； 四个方向上的点应该存在，且大于i,j，表示以i,j开始的点最长路径，递归的结束条件不用判断，因为
dp[][]最大数位置肯定 直接结束，随后次大值肯定能结束，以此类推，所以可以执行，但自下而上动态规划不好写。因为要确定这些数的大小，麻烦。
#include<iostream> #include<memory.h> using namespace std; int dp[101][101]; int arr[101][101]; int c; int r; int x[]={0,1,0,-1}; int y[]={1,0,-1,0}; bool isvalid(int row,int col,int r_off,int c_off) //找到没有超过矩阵范围，且在点比arr[i][j]大 { int newr=row+r_off; int newc=col+c_off; if(newr>=0&&newr<r&&newc>=0&&newc<c&&arr[row][col]<arr[newr][newc]) { return true; } return false; } int fun(int row,int col) { int tem=0; for(int i=0;i<4;i++) { if(isvalid(row,col,x[i],y[i])) { int tfun=fun(row+x[i],col+y[i]); if(tem<tfun) { tem=tfun; } } } return tem+1; } //备忘录，自顶向下动态规划，dp矩阵防止重复计算 int fun2(int row,int col) { if(dp[row][col]>0) return dp[row][col]; int tem=0; for(int i=0;i<4;i++) { if(isvalid(row,col,x[i],y[i])) { int tfun=fun(row+x[i],col+y[i]); dp[row+x[i]][col+y[i]]=tfun; if(tem<tfun) { tem=tfun; } } } return tem+1; } int main() { int len; cin>>len; while(len--) { memset(dp,0,sizeof(dp)); cin>>r>>c; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { cin>>arr[i][j]; } } int max=0; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { int tem= fun2(i,j); //以i,j为开始的最长点数 if(max<tem) max=tem; } } cout<<max<<endl; } return 0; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。