【题目链接】：click here~~
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
问题描述
小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会，于是他们来到了大洋彼岸的美国。美国人民的生活非常有意思，经常会有形形色色、奇奇怪怪的活动举办，这不，小Hi和小Ho刚刚下飞机，就赶上了当地的迷宫节活动。迷宫节里展览出来的迷宫都特别的有意思，但是小Ho却相中了一个其实并不怎么像迷宫的迷宫——因为这个迷宫的奖励非常丰富~
于是小Ho找到了小Hi，让小Hi帮助他获取尽可能多的奖品，小Hi把手一伸道：“迷宫的介绍拿来！”
小Ho选择的迷宫是一个被称为“数字三角形”的n(n不超过200)层迷宫，这个迷宫的第i层有i个房间，分别编号为1..i。除去最后一层的房间，每一个房间都会有一些通往下一层的房间的楼梯，用符号来表示的话，就是从第i层的编号为j的房间出发会有两条路，一条通向第i+1层的编号为j的房间，另一条会通向第i+1层的编号为j+1的房间，而最后一层的所有房间都只有一条离开迷宫的道路。这样的道路都是单向的，也就是说当沿着这些道路前往下一层的房间或者离开迷宫之后，小Ho没有办法再次回到这个房间。迷宫里同时只会有一个参与者，而在每个参与者进入这个迷宫的时候，每个房间里都会生成一定数量的奖券，这些奖券可以在通过迷宫之后兑换各种奖品。小Ho的起点在第1层的编号为1的房间，现在小Ho悄悄向其他参与者弄清楚了每个房间里的奖券数量，希望小Hi帮他计算出他最多能获得多少奖券。
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为一个正整数n,表示这个迷宫的层数。
接下来的n行描述这个迷宫中每个房间的奖券数，其中第i行的第j个数代表着迷宫第i层的编号为j的房间中的奖券数量。
测试数据保证，有100%的数据满足n不超过100
对于100%的数据，迷宫的层数n不超过100
对于100%的数据，每个房间中的奖券数不超过1000
对于50%的数据，迷宫的层数不超过15（小Ho表示2^15才3万多呢，也就是说……）
对于10%的数据，迷宫的层数不超过1（小Hi很好奇你的边界情况处理的如何？~）
对于10%的数据，迷宫的构造满足：对于90%以上的结点，左边道路通向的房间中的奖券数比右边道路通向的房间中的奖券数要多。
对于10%的数据，迷宫的构造满足：对于90%以上的结点，左边道路通向的房间中的奖券数比右边道路通向的房间中的奖券数要少。
输出
对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的最多奖券数。
样例输入526 41 2 84 0 9 66 5 5 3 6样例输出28
【思路】：
“我们可以来分分情况，我们要搜索所有的路径，然后依次计算每条路径的收益，这是我们现在的问题模型是不是？”小Hi问道。
小Ho点头：“仔细分析这个迷宫的话，我们有两种搜索方法，一种是深度优先搜索，就像这幅图画的一样，我们先试着顺着每个房间的第一条路一直下去，一直走到最后一层，然后返回至倒数第二层，选择第二条路走到最后一个房间，然后返回到倒数第三层，选择第二条路走到倒数第二层，然后选择第一条路走到最后一层……期间维护已经走过的房间的奖券之和sum，然后每次到达最后一层的房间的时候将sum与全局最优解ans进行比较，如果sum>ans的话就用sum替换ans。这样在所有路径都计算过一遍之后，Ans中存储的就是我们要的答案了~~而第二种……”
“先别说第二种，我们来看看这种方法有什么办法优化么~”小Hi打断了小Ho的喋喋不休。
“哦，但是该怎么优化呢？”小Ho问道。
“老规矩，我们来看看这个过程中有什么冗余计算~”小Hi还是那一套说辞，也不担心小Ho听了这么多遍听厌：“看这张图，当你枚举到绿色的‘-》右-》左’这样一条路径的时候，是不是发现它和红色的‘-》左-》右’这条路径一样都到达了第三层的第二个房间？”
“是的！”
“在你枚举到绿色路径的时候，是不是红色路径已经被枚举过了？”小Hi接着问道。
“没错！“
“那么你看，绿色路径的奖券和是8，红色路径的奖券和是10，而你们都处于了相同的结点——第3层的第2个房间上，这时候无论你绿色路径接下来延续出什么样的路径，我将从第3层第2个房间开始的这一段连在红色路径之后的话，奖券和都会要比绿色路径要多？”小Hi继续问。
“嗯……对的~”
“而这些路径中的最优值都肯定不超过Ans，不然Ans就会在当时变得和它们一样，这不就说明了绿色路径无论接下来如何走，都不可能对Ans造成任何变化，那我们是不是完全可以不进行接下来的计算了呢？”小Hi做出了最后的结论。
“是的……为了进行这样的优化，我们需要记录一个值best(i, j)——当前搜索过的路径中到达第i层第j个房间时最多能获取多少奖券，然后在每次进入一个房间的时候，都检查当前的sum与best(i, j)的大小关系，如果sum小于等于best(i, j)的话，就没有必要继续搜索了呢。比如在之前的例子中，当通过绿色路径到达第3层第2个房间的时候，best(i, j)=10，而sum = 8，所以是没有必要继续往下搜索的。”聪明的小Ho很快就将这个算法总结了出来。
“而这种做法，由于是通过之前的记忆来避免不必要的搜索，所以被大家称为‘记忆化搜索’”小Ho笑道：“这样，只要不是那种非常坏的卡你的情况——比如第i层第j个房间的奖券数是j这种，都能够在O(n^2)的复杂度通过了呢。”
“而如果我先右再左呢？”小Ho不死心。
愚者用肉体监视心灵，智者用心灵监视肉体
