bnuoj 29065 鸣人的查克拉

旧城等待， 2022-08-26 08:03 22阅读 0赞

# 鸣人的查克拉 #

Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Prev][] [Submit][] [Status][] [Statistics][] [Discuss][] [Next][]

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

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 ##

做这道题目深感理解力不足啊，读了好多遍还是不明白题目的意思啊，当时是直接模拟过的。其实是dp

动态的维护一个区间的值，还是理解不够啊。。。欢迎同样有疑问的和我讨论。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int c, n;
        while (scanf("%d %d", &c, &n) != EOF)
        {
            int low_bound = -100000;
            int up_bound = 100000;
            int t = 0,x;
            int prev = 0;
            int curr = c;
            for (int i = 0; i < n; ++i)
            {
                scanf("%d", &x);
                t = max(t, low_bound + x);  ///第二次结束最大值
                if (curr >= x)   ///当前能不能发动、
                {
                    up_bound = min(up_bound, x);  ///区间最小值
                    low_bound = max(low_bound, prev - x);   ///第二次发动
                }
                prev = max(prev, x - up_bound);   ///第一次发动结束得到的最大值
                curr = prev + c;   ///
                //printf("%d %d %d %d %d\n",t,up_bound,low_bound,prev,curr);
            }
            printf("%d\n", t + c);
        }
        return 0;
    }

[Prev]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=29064
[Submit]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=29065#
[Status]: http://www.bnuoj.com/bnuoj/status.php?showpid=29065
[Statistics]: http://www.bnuoj.com/bnuoj/problem_stat.php?pid=29065
[Discuss]: http://www.bnuoj.com/bnuoj/discuss.php?pid=29065
[Next]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=29066