题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29065
Descripion
《火影忍者》中，在忍者们使用忍术的时候，需要一定的查克拉（可以看成是一种体力值）。在战斗前，大家都希望提高自己的查克拉。
鸣人发明了一种忍术，可以在短时间内提高查克拉。
在使用忍术前，鸣人需要做一个仪式，这个仪式决定之后每个时刻的一个查克拉值。这些值的使用规则是：如果在某个时刻发动这个忍术，鸣人需要先消耗该时刻的查克拉值；在某个时候结束这个忍术，鸣人能获得该时刻的查克拉值（忍术必须先发动才能结束）。当然，如果某时刻鸣人具有的查克拉值少于该时刻的查克拉值，那么鸣人是不能发动该忍术的。
由于鸣人对这个忍术还不能很好地控制，所以他最多只能发动两次该忍术，并且两次忍术不能同时发动，也就是说必须结束一次忍术才能发动下一次（第一次结束时可以立即发动第二次）。
现在仪式已经做完了，鸣人知道了自己的查克拉的初始值，以及各个时刻的查克拉值，如果他最多可以发动两次该忍术（他也可以选择发动一次或者不发动），那么他最多能达到的查克拉值是多少？
Input
输入数据只有一组，第一行包括两个整数C(0<=C<=100,000)和N(N<=10,000)，表示鸣人的初始查克拉值以及仪式决定的时刻的个数。
接下来有N行，第i行包含一个整数Ai (0<=ai<=100,000)，表示第i个时刻的查克拉值。
Output
输出一个整数，表示鸣人在使用忍术后能到达的最大的查克拉值。
Sample Input
Sample Input1
10 5
1
2
3
2
5
Sample Input2
10 2
11
13
Sample Output
Sample Output1
15
Sample Output2
10
Source
第十一届北京师范大学程序设计竞赛决赛
Author
zhanyu
注意一点：第一次发动停止之后可以立即进行第二次发动，也就是说同一时刻，可以同时是第一次发动的结束与第二次发动的开始。
很好的一题，可dp可记忆化搜索，可惜当时我一个都没想到=3=
当时在赛场上搞了个O(n^2)的解法出来，理所当然的TLE了……Orz
以下参考别人的解法，个人觉得思路很巧妙，详细请看注释：
1 #include <cstdio>
2 #include <algorithm>
3
4 using namespace std;
5
6 const int MAXN =
10010;
7 const int INF =
1 <<
30;
8
9 int C, N;
10 int a[MAXN];
11 int Get[MAXN];
12
13 void solved()
14 {
15 int mini =
INF;
16 int ans =
C;
17
18 for (
int i =
1; i <= N; ++
i )
19 {
20 mini = min( mini, a[i] );
//动态维护区间[1, i]的最小值
21 if ( mini <= C && mini <= a[i] ) Get[i] = C - mini + a[i];
//选择在i点停止发动所能得到的能量
22 else Get[i] =
C;
23
24 ans = max( ans, Get[i] );
//动态更新所能达到的最大值
25 }
26
27 //得到第一次发动，区间[1, i]所能获得的最大能量，不必关心该区间内哪里开始哪里结束
28 for (
int i =
2; i <= N; ++
i )
29 Get[i] = max( Get[i -
1], Get[i] );
30
31 int maxi = -
INF;
32 for (
int i =
1; i <= N; ++i )
//第二次发动
33 {
34 ans = max( ans, maxi + a[i] );
//动态更新在第i时刻发动停止所得到的最大值
35 if ( Get[i] - a[i] >=
0 )
//动态维护在第i时刻发动所剩余能量的最大值
36 maxi = max( maxi, Get[i] -
a[i] );
37 }
38
39 printf(
"%d\n", ans );
40
41 return;
42 }
43
44 int main()
45 {
46 while ( ~scanf(
"%d%d", &C, &
N ) )
47 {
48 for (
int i =
1; i <= N; ++
i )
49 scanf(
"%d", &
a[i] );
50
51 solved();
52 }
53 return 0;
54 }
转载于:https://www.cnblogs.com/GBRgbr/archive/2013/05/03/3057844.html
相关资源：数据结构—成绩单生成器
