题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1078
题目大意：给你一个二维数组a，从(0,0)开始，每次最多走k步（智能垂直或水平走）， 要求下一步a(x2, y2) > a(x1, y1)上一步， 把这条路径上的所有a值加起来， 问能得到最大的值是多少？
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <set> 8 #include <map> 9 #include <vector> 10 using namespace std; 11 12 int a[110][110], dp[110][110], n, k; 13 int to[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; 14 int dfs(int sx, int sy) 15 { 16 int x, y, max = 0; 17 if(dp[sx][sy] != 0) 18 return dp[sx][sy]; 19 for(int i = 0; i < 4; i++) 20 { 21 for(int j = 1; j <= k; j++) 22 { 23 x = sx + to[i][0] * j; 24 y = sy + to[i][1] * j; 25 if(x >= 0 && x < n && y >= 0 && y < n && a[sx][sy] < a[x][y]) 26 { 27 int t = dfs(x, y); 28 if(t > max){ 29 max = t; 30 //cout << x << " " << y << " "<< dp[x][y] << endl; 31 } 32 } 33 } 34 } 35 dp[sx][sy] = a[sx][sy] + max; 36 37 return dp[sx][sy]; 38 } 39 int main() 40 { 41 while(~scanf("%d %d", &n, &k)) 42 { 43 if(n == -1 && k == -1) 44 break; 45 for(int i = 0; i < n; i++) 46 for(int j = 0; j < n; j++) 47 scanf("%d", &a[i][j]); 48 memset(dp, 0, sizeof(dp)); 49 printf("%d ", dfs(0, 0)); 50 } 51 return 0; 52 }