博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
7I - 数塔
阅读量:5823 次
发布时间:2019-06-18

本文共 1207 字,大约阅读时间需要 4 分钟。

在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? 
已经告诉你了,这是个DP的题目,你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。 

Output

对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。 

Sample Input

1573 88 1 0 2 7 4 44 5 2 6 5

Sample Output

30 // 递归
1 #include
2 3 int n, t[100][100]; 4 5 int tower(int i, int j) 6 { 7 if(i==n-1) return t[i][j]; 8 if(tower(i+1,j)>tower(i+1,j+1)) 9 return tower(i+1,j)+t[i][j];10 else11 return tower(i+1,j+1)+t[i][j];12 }13 14 int main()15 {16 int c;17 scanf("%d", &c);18 while(c--)19 {20 scanf("%d", &n);21 for(int i=0;i
Time Limit Exceeded
//
1 #include
2 #include
3 int n, t[100][100], d[100][100]; 4 5 int tower(int i, int j) 6 { 7 if(d[i][j]>=0) return d[i][j]; 8 return d[i][j] = t[i][j] + (i==n-1?0:(tower(i+1,j)>tower(i+1,j+1)?tower(i+1,j):tower(i+1,j+1))); 9 }10 11 int main()12 {13 int c;14 scanf("%d", &c);15 while(c--)16 {17 scanf("%d", &n);18 for(int i=0;i
AC

 

转载于:https://www.cnblogs.com/goldenretriever/p/10357105.html

你可能感兴趣的文章
android 国内工具集
查看>>
建筑效果图素材站SKALGUBBAR
查看>>
python gzip 压缩/解压缩 字符串
查看>>
Android framework系统默认设置修改
查看>>
android staticlayout使用讲解
查看>>
ecshop用户登录问题及ecshop购物车问题解决办法
查看>>
一个Servlet编码过滤器
查看>>
韩国Linux即相关软件镜像服务器
查看>>
jquery 或 js如何截取字符串
查看>>
Linux网络编程(第2版)
查看>>
修改grub2系统选择菜单等待时间(Debian 7)
查看>>
C++-成员指针
查看>>
C-pthread2
查看>>
yum挂载本地光盘镜像
查看>>
Linux下Sed命令的用法
查看>>
我的友情链接
查看>>
反lj邮件防火墙的核心技术分析1
查看>>
Android初学者的迷茫
查看>>
2013回忆录,从大学到工作
查看>>
java2:原理数据类型
查看>>