/ Vijos / 题库 /

The Moment-遇见

The Moment-遇见

背景

听见 冬天的离开
我在某年某月 醒过来
我想 我等 我期待
未来却不能因此安排
阴天 傍晚 车窗外
未来有一个人在等待

燕姿必须赶到一个地方去见xx, 在路上,她遇到了一座特殊的桥………

描述

燕姿在桥的这一端,而xx在桥的另一端。这座桥非常特殊,桥面是由2N-1个方格组成的,每个方格里写有一个数码Ai(-50<=Ai<=50)。如下是N=4时的情况。可以认为燕姿从最下面出发。每一次,她可以向上跳到与自己所在方格相临的其中一个方格内(例如在最下面的7中,可以跳到上一行的10和8中)。当燕姿跳到最顶端的方格后,她就不能再移动了。(在未到顶端前,不允许跳到表格外。)每在一格内,都要把格内的数字写下来。

但是,仅仅到达顶端是不够的。桥会向对岸的xx询问一个数字k,燕姿到达顶端后,拿出写下来的数字,可以在任意两个数字间添加“+”或“-”号,使得计算的结果m最接近k。经过桥的判断,如果对于桥上的方格m是最接近k的数字,那么燕姿就可以通过桥和xx相遇,否则………
(为了让燕姿能更容易地通过,xx给出的数字总是0)你的任务,就是帮助燕姿找出这个最接近k的m.
图片

最优解7+8+(-5)+(-2)-5-1-2=0

或7+10+(-7)-6+(-3)-3+2=0
或7+10+(-5)-10-5+1+2=0
或+10+(-5)+(-2)-5-3-2=0

格式

输入格式

输入的第一行是N(1<=N<=30),接下来2N-1行给出了表格中每行的每个方格中的数字,第i+1行的第j个数字对应于表格中第i行的第j个数字。文件中第二行的数字表示的是表格顶端的方格中的数字。所有的数字都是整数,同一行相邻的两个数字间用空格符隔开。

输出格式

输出只有一行,是你所求出的最接近零的计算结果的绝对值

样例1

样例输入1

4                                    
2
3 1
-3 5 7
6 10 -2 20
-7 -5 -8
10 8 
7

样例输出1

0

限制

每点1s

来源

孙燕姿
图片

信息

ID
1280
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
1118
已通过
331
通过率
30%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

孙燕姿NOIP2006模拟赛