|
|
|
|
背景 Background |
|
|
|
LOGGIC做了初级dp后，觉得数字三角形太简单，所以加强了一下
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
蜗牛小笨（BEN）遇到一个类似这样的迷宫：
1
1 2
2 1 1
这个迷宫是一个等腰直角三角形，每个点上都有一个数字，蜗牛有一次使用魔法的机会。
蜗牛行进的方式：
1、行走：蜗牛进行行走，可以走到下一行、同一列或者下一行、右边一列。
2、魔法：只能使用一次，可以从第x行飞到第(x+1)行的任意一列。
要求：蜗牛所经之路的数字和最大。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行是一个数n，代表这个三角形的腰的长度。
第2～(n+1)行中，第m行有(m-1)个数，代表这些数字。
输入数据保证：
0<n<300
各个数字不超过2*maxlongint
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
一个数：最大的数字和
输出数据保证不超过2*maxlongint
|
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点1s
|
|
|
|
|
|
|
|
注释 Hint |
|
|
|
样例解释：
三角形
1
\
1 \->2 (正常行进)
/
2<-/ 1 1 (魔法)
所以，答案是1+2+2=5
(看不清请复制到记事本中)
|
|
|
|
|
|
|
|
来源 Source |
|
|
|
LOGIC原创，第一次出题，这个测试数据很多哦
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1519 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
