鸣人的查克拉
Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Font Size:
+
-
+
-
Type:
None Graph Theory
2-SAT Articulation/Bridge/Biconnected Component
Cycles/Topological Sorting/Strongly Connected Component
Shortest Path
Bellman Ford Dijkstra/Floyd Warshall
Euler Trail/Circuit
Heavy-Light Decomposition
Minimum Spanning Tree
Stable Marriage Problem
Trees
Directed Minimum Spanning Tree
Flow/Matching Graph Matching
Bipartite Matching
Hopcroft–Karp Bipartite Matching
Weighted Bipartite Matching/Hungarian Algorithm
Flow
Max Flow/Min Cut
Min Cost Max Flow
DFS-like Backtracking with Pruning/Branch and Bound
Basic Recursion
IDA* Search Parsing/Grammar
Breadth First Search/Depth First Search
Advanced Search Techniques
Binary Search/Bisection
Ternary Search
Geometry
Basic Geometry Computational Geometry
Convex Hull
Pick's Theorem Game Theory
Green Hackenbush/Colon Principle/Fusion Principle
Nim
Sprague-Grundy Number
Matrix Gaussian Elimination
Matrix Exponentiation
Data Structures
Basic Data Structures
Binary Indexed Tree
Binary Search Tree
Hashing Orthogonal Range Search
Range Minimum Query/Lowest Common Ancestor
Segment Tree/Interval Tree
Trie Tree
Sorting Disjoint Set
String
Aho Corasick Knuth-Morris-Pratt
Suffix Array/Suffix Tree
Math
Basic Math Big Integer Arithmetic
Number Theory
Chinese Remainder Theorem
Extended Euclid
Inclusion/Exclusion
Modular Arithmetic
Combinatorics Group Theory/Burnside's lemma
Counting
Probability/Expected Value
Others Tricky
Hardest Unusual
Brute Force
Implementation Constructive Algorithms
Two Pointer
Bitmask Beginner
Discrete Logarithm/Shank's Baby-step Giant-step Algorithm
Greedy
Divide and Conquer
Dynamic Programming
None Graph Theory
2-SAT Articulation/Bridge/Biconnected Component
Cycles/Topological Sorting/Strongly Connected Component
Shortest Path
Bellman Ford Dijkstra/Floyd Warshall
Euler Trail/Circuit
Heavy-Light Decomposition
Minimum Spanning Tree
Stable Marriage Problem
Trees
Directed Minimum Spanning Tree
Flow/Matching Graph Matching
Bipartite Matching
Hopcroft–Karp Bipartite Matching
Weighted Bipartite Matching/Hungarian Algorithm
Flow
Max Flow/Min Cut
Min Cost Max Flow
DFS-like Backtracking with Pruning/Branch and Bound
Basic Recursion
IDA* Search Parsing/Grammar
Breadth First Search/Depth First Search
Advanced Search Techniques
Binary Search/Bisection
Ternary Search
Geometry
Basic Geometry Computational Geometry
Convex Hull
Pick's Theorem Game Theory
Green Hackenbush/Colon Principle/Fusion Principle
Nim
Sprague-Grundy Number
Matrix Gaussian Elimination
Matrix Exponentiation
Data Structures
Basic Data Structures
Binary Indexed Tree
Binary Search Tree
Hashing Orthogonal Range Search
Range Minimum Query/Lowest Common Ancestor
Segment Tree/Interval Tree
Trie Tree
Sorting Disjoint Set
String
Aho Corasick Knuth-Morris-Pratt
Suffix Array/Suffix Tree
Math
Basic Math Big Integer Arithmetic
Number Theory
Chinese Remainder Theorem
Extended Euclid
Inclusion/Exclusion
Modular Arithmetic
Combinatorics Group Theory/Burnside's lemma
Counting
Probability/Expected Value
Others Tricky
Hardest Unusual
Brute Force
Implementation Constructive Algorithms
Two Pointer
Bitmask Beginner
Discrete Logarithm/Shank's Baby-step Giant-step Algorithm
Greedy
Divide and Conquer
Dynamic Programming
Tag it!
《火影忍者》中，在忍者们使用忍术的时候，须要一定的查克拉（能够看成是一种体力值）。在战斗前，大家都希望提高自己的查克拉。
鸣人发明了一种忍术，能够在短时间内提高查克拉。
在使用忍术前，鸣人须要做一个仪式，这个仪式决定之后每一个时刻的一个查克拉值。这些值的使用规则是：假设在某个时刻发动这个忍术。鸣人须要先消耗该时刻的查克拉值；在某个时候结束这个忍术。鸣人能获得该时刻的查克拉值（忍术必须先发动才干结束）。
当然，假设某时刻鸣人具有的查克拉值少于该时刻的查克拉值。那么鸣人是不能发动该忍术的。
因为鸣人对这个忍术还不能非常好地控制，所以他最多仅仅能发动两次该忍术。而且两次忍术不能同一时候发动，也就是说必须结束一次忍术才干发动下一次（第一次结束时能够马上发动第二次）。
如今仪式已经做完了。鸣人知道了自己的查克拉的初始值，以及各个时刻的查克拉值。假设他最多能够发动两次该忍术（他也能够选择发动一次或者不发动）。那么他最多能达到的查克拉值是多少？
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
#include<stdio.h>
#define N 10100
int main()
{
int C,n,a[N],dp[2][N],min,max,ans;
scanf("%d%d",&C,&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
min=a[0];dp[0][0]=0; ans=0;
for(int i=1;i<n;i++)//从前往后，第i个位结束
if(min<=C)
{
if(min>a[i])min=a[i];
dp[0][i]=a[i]-min;
if(ans<dp[0][i])ans=dp[0][i];
dp[0][i]=ans;
}
else
{
if(min>a[i])min=a[i];
dp[0][i]=ans;
} int sum=dp[0][n-1]+C;
max=a[n-1]; dp[1][n-1]=0; ans=0;
for(int i=n-2;i>0;i--)//从后往前，第i个位開始
if(dp[0][i-1]+C>=a[i])
{
if(max<a[i])max=a[i];
dp[1][i]=max-a[i];
if(ans<dp[1][i])ans=dp[1][i];
dp[1][i]=ans;
if(sum<dp[0][i-1]+C+dp[1][i])
sum=dp[0][i-1]+C+dp[1][i];
}
else
{
if(max<a[i])max=a[i];
dp[1][i]=ans;
if(sum<dp[0][i-1]+C+dp[1][i])
sum=dp[0][i-1]+C+dp[1][i];
}
printf("%d\n",sum);
}