由于这两个题目有递进关系所以把他们写在一个博客里面，希望对各位有帮助！
?
?
1
3 4
1 10 8 8
0 0 1 8
0 27 0 4
输出：
?
?
Scenario #1:
42
题目大意：就是从一个矩阵的左上角走到它的右下角，矩阵的每一个元素都有一个非0值，只有三个方向可以走向右、向下、向右下。求到达右下角的最大值。
?
刚开始看到的时候往搜索方向想，一直想不通啊！后来去网上看了一下，原来用动规呀呀
AC代码：
?
#include
#include
#include
using namespace std; int a[1001][1001]; int dp[1001][1001];//dp[i][j]用来表示第i行第j列这个位置值的最大值。 int max(int x,int y,int z) { if(x
?
http://acm.hdu.edu.cn/showproblem.php?pid=2571
题目大意：也是给出一个矩阵，以及每个元素的值，与上题不同的是这里的值可以为负的（给dp初始化的时候要注意），走的方向是向下、向右（向右可以是一步也可以是这个位置列的K倍）。
这个题目看似与上题没太大差别，实际上也是差别不大，但是有个地方还是得注意一下的（K）。
这个题目用记忆化搜索的话会跟简单方便，但是由于本人还不会使用。。。这里就不贴关于记忆化搜索的代码了，以后学会了一定补一个。
AC代码：
?
#include
#include
#include
#include
using namespace std; #define M -999999 int a[21][1005]; int dp[21][1005]; int max(int x,int y) { return x>y?x:y; } int main() { int t,r,c,i,j,k; scanf(%d,&t); while(t--) { scanf(%d%d,&r,&c); for(i=1;i<=r;i++) for(j=1;j<=c;j++) scanf(%d,&a[i][j]); for(i=0;i<=r;i++) dp[i][0]=M; for(i=0;i<=c;i++) dp[0][i]=M; dp[0][1]=0; dp[1][0]=0; for(i=1;i<=r;i++) { for(j=1;j<=c;j++) { dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//先比较走一格的。 k=2; while(j/k>0)//这里是表示可以从哪个点跳到该点。 { if(j%k==0)//如果可以跳跃 dp[i][j]=max(dp[i][j],dp[i][j/k]+a[i][j]);//比较跳的。 k+=1; } } } printf(%d ,dp[r][c]); } return 0; }
?
?
?