数塔-动态规划-ccf

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main(){
 5     int n;//数塔层数 
 6     cin>>n;
 7 if(n>0){
 8     float a[n][n],c[n][n];//a，c记录数组
 9     //输入数组 
10     for(int i=0;i<n;i++){
11         for(int j=0;j<=i;j++){
12             cin>>a[i][j];
13             c[i][j]=a[i][j];
14         }
15     }
16     //b记录每层数字所加上的下一层数字对应的列数 
17     int b[n-1][n-1];
18     //对a进行从下到上的层加，同时用b记录 
19     for(int i=n-1;i>0;i--){
20         for(int j=0;j<i;j++){
21             if(a[i][j]<a[i][j+1]){
22                 b[i-1][j]=j+1;
23                 a[i-1][j]+=a[i][j+1];
24             }
25             else{
26                 b[i-1][j]=j;
27                 a[i-1][j]+=a[i][j];
28             }
29         }
30     }
31     //输出 
32     cout<<a[0][0]<<endl;
33     cout<<c[0][0];
34     int j=0; 
35     for(int i=0;i<n-1;i++){
36                 j=b[i][j];
37                 cout<<' '<<c[i+1][j];
38             }
39 }
40     
41     return 0;
42 }

 

题目：

给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。

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

【输入形式】

输入时第一行一个整数n，表示该数塔的行数，其余n行表示该塔每行的数值

【样例输入】

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

【输出形式】

输出包含两行，第一行为最大路径上的数值之和， 第二行n个数字为从上而下最大路径数值

【样例输出】

59
9 12 10 18 10

---

解题思路：

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

自下而上判断，从最后一行（第n行）开始，
n-1行每个数字加上所对应n行的数中最大的数，
循环这一步骤直至第n=1，得到所求最大和

---

代码实现：
见评论

---

注意：
1、输入的合法性分析
2、数塔中数据类型
3、数塔中重复数字的处理