AOJ 806.算法期末考试B(动态规划)

227

题目



Description  


给定一个数塔,其存储形式为如下所示的下三角矩阵。在此数塔中,从顶部出发,在每一节点可以选择向下走还是向右下走,一直走到底层。请找出一条路径,使路径上的数值和最大。


Input  


多组输入,EOF结束,对于每组输入第一行为一个数字n表示数塔的高度,之后为n行,每行有1,2,3...n个数字(数字范围-100到100),表示数塔中的数字


Output  


对于每组输入输出一行,表示最大值。


Sample Input  


5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16


Sample Output  


59


题解



动态规划问题,将东西输入后
从下往上刷(n-1 ~ 0)。计算到大第i层的第j个位置的最大值
dp[i][j] = dp[i][j] + max(dp[i+1][j],dp[i+1][j+1])

即每一个位置应该与能到达它的最大位置相加

最后dp[0][0]就是答案


#代码
/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
const int maxn = 1000;
 
int Map[maxn][maxn];
 
bool Do() {
    int n;
     
    if(scanf("%d",&n) == EOF)
        return false;
 
    memset(Map,0,sizeof(Map));
 
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= i;j++)
            scanf("%d",&Map[i][j]);
 
    for(int i = n - 1;i > 0;i--)
        for(int j = 1;j <= i;j++)
            Map[i][j] += max(Map[i + 1][j],Map[i + 1][j + 1]);
    printf("%d\n",Map[1][1]);
    return true;
}
 
int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论