1258：【例9.2】数字金字塔 回溯搜索(超时)解法示例
1258：【例9.2】数字金字塔
时间限制: 1000 ms 内存限制: 65536 KB
提交数:63658 通过数: 38747
【题目描述】
观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。
【输入】
第一个行包含R(1≤R≤1000)，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
【输出】
单独的一行，包含那个可能得到的最大的和。
【输入样例】
5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11【输出样例】
86本题其实是为了练习动态规划而设，但这题也挺适合练习回溯搜索，有必要写一下代码:
（回溯搜索运行超时，请使用动态规划解题）
#include <bits/stdc++.h> using namespace std; int g[1001][1001]; int temp[1001]; int r; int sum=0,maxx=0; void FS(int i,int j){ temp[i]=g[i][j]; if(i+1<r){ FS(i+1,j); FS(i+1,j+1); } else { sum=0; for(int j=0;j<r;j++){ sum+=temp[j]; printf("%2d ",temp[j]);//输出所有路径 测试用 } printf(" = %d \n",sum); if(sum>maxx)maxx=sum; } } int main(int argc, char** argv) { memset(g,0,sizeof(g)); cin>>r; for(int i=0;i<r;i++){ for(int j=0;j<=i;j++){ cin>>g[i][j]; } } //搜索算法 FS(0,0); //计算每条路径的数值和 printf("%d",maxx); return 0; }