hdu 1078
程序员文章站
2022-07-02 16:25:39
思路:能够向四个方向前进,同时前进步数不超过m。那么,在遍历的时候运用一层循环将不超过m步的都一一列举出来。 同时,在遍历的过程中需要记录数据形成记忆是搜索。 ......
1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 int A[150][150]; 6 int dp[150][150]; 7 int maxv=0; 8 int n,m; 9 int tr[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};//上下左右 10 int Find(int x,int y) 11 { 12 if(dp[x][y]!=0) return dp[x][y]; 13 for(int i=0; i<4; i++) 14 { 15 for(int j=1; j<=m; j++) 16 { 17 int x1,y1; 18 if(tr[i][0]==1) 19 { 20 x1=x+j; 21 y1=y; 22 } 23 if(tr[i][0]==-1) 24 { 25 x1=x-j; 26 y1=y; 27 } 28 if(tr[i][1]==-1) 29 { 30 x1=x; 31 y1=y-j; 32 } 33 if(tr[i][1]==1) 34 { 35 x1=x; 36 y1=y+j; 37 } 38 if(x1>=1&&x1<=n&&y1>=1&&y1<=n&&A[x][y]<A[x1][y1]) 39 { 40 dp[x][y]=max(Find(x1,y1)+A[x1][y1],dp[x][y]); 41 } 42 } 43 } 44 return dp[x][y]; 45 } 46 int main() 47 { 48 49 while(cin>>n>>m) 50 { 51 maxv=0; 52 if(n==-1&&m==-1) break; 53 memset(dp,0,sizeof(dp)); 54 memset(A,0,sizeof(A)); 55 for(int i=1; i<=n; i++) 56 { 57 for(int j=1; j<=n; j++) 58 { 59 cin>>A[i][j]; 60 } 61 } 62 Find(1,1); 63 cout<<dp[1][1]+A[1][1]<<endl; 64 } 65 66 }
上一篇: html基础标签
下一篇: A*算法在OI中的应用
推荐阅读
-
hdu--1232 继续通畅工程
-
HDU 2256Problem of Precision(矩阵快速幂)
-
湫湫系列故事——设计风景线 HDU - 4514
-
HDU6315 Naive Operations(线段树 复杂度分析)
-
【题解】hdu1506 Largest Rectangle in a Histogram
-
C - Monkey and Banana HDU 1069( 动态规划+叠放长方体)
-
HDU 1052(田忌赛马 贪心)
-
hdu-1338 game predictions(贪心题)
-
致初学者(四):HDU 2044~2050 递推专项习题解
-
C语言BFS--Find a way(Hdu 2612)