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 sum0,maxx0; void FS(int i,int j){ temp[i]g[i][j]; if(i1r){ FS(i1,j); FS(i1,j1); } else { sum0; for(int j0;jr;j){ sumtemp[j]; printf(%2d ,temp[j]);//输出所有路径 测试用 } printf( %d \n,sum); if(summaxx)maxxsum; } } int main(int argc, char** argv) { memset(g,0,sizeof(g)); cinr; for(int i0;ir;i){ for(int j0;ji;j){ cing[i][j]; } } //搜索算法 FS(0,0); //计算每条路径的数值和 printf(%d,maxx); return 0; }