求AC代码及详细解释(也就是推导思路)
Wujitu的RP守恒时间限制:1500 ms | 内存限制:8192 KB
描述
话说天下的RP是守恒的,你的RP高了,我的RP可能就低了,你今天RP高了,明天RP可能就低了。我们的RP总是在高高低低中不断变化。有些事情做了是可以涨RP的,有的事情做了是要降RP的。
Wujitu在发现了这个道理后,决定在期末考试前多多积累人品。他发现,他做的每件事情对RP有如下影响:
(1) 他做了的第一件事情是涨RP的
(2) 如果他做的上一件事情是涨RP的,那么他做的下一件事情是降RP的
(3) 如果他做的上一件事情是降RP的,那么他做的下一件事情是涨RP的
Wujitu现在积攒的人品是0。涨RP记为RP值增加,降RP记为RP值减少。
Wujitu在期末考试前有N件事情可以做,每件事情都有自己的RP系数。对于这些事情,Wujitu只可以有两种选择:做,不做。事情的先后顺序是一定的,也就是说Wujitu只可以按照给定好的顺序选择做不做该事情。
现在请你帮助Wujitu在期末考试之前,积攒到最多的RP。
输入
每组数据包括两行,第一行有一个整数N(N<=1000000),代表有N件事情;第二行有N个正整数,代表每件事情的RP值Ri[正数]
Ri<=1000000
输出
输出结果仅包含一个整数,即Wujitu在期末前能积攒的最大RP值
样例输入
1
1
4
1 3 1 2
样例输出
1
4
希望能给出AC代码以及详细解释,这道DP题好像有后效应,不知道怎么做,望大牛赐教
在下面提交,谢谢!
http://www.