BOSS战-普及综合练习3-积木大赛

题目链接:https://www.luogu.org/problemnew/show/P1969

题意理解

很容易发现：如果一个数列，先递增，再递减，或者只有递增（递减），那么操作次数就是其中的最大值。

然后很容易观察出，结果与若干个极大值减去极小值的和有关。为了更方便理解，可以在最前面加一个0。那么必然就是一个极小值对应一个极大值。至于最后一段如果极大值后面还有数字，那么是不影响结果的。加粗的部分已经该说明了。

另外，假设 ai,⋯,aj a i , ⋯ , a j 是连续的数，那么 aj−ai=(aj−aj−1)+(aj−1−aj−2)+⋯+(ai+1−ai) a j − a i = ( a j − a j − 1 ) + ( a j − 1 − a j − 2 ) + ⋯ + ( a i + 1 − a i ) 。此时我们取 ai a i 为极小值， aj a j 为极大值，就得到了下面的代码。

代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int maxn = ;
    static int N;
    static int[] h = new int[maxn];
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        int res = ;
        N = fs.nextInt();
        for(int i = ; i <= N; i++) {
            h[i] = fs.nextInt();
            if(h[i] > h[i-]) {
                res += h[i] - h[i-];
            }
        }
        System.out.println(res);
    }

    public static class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public void eat(String s) {
            st = new StringTokenizer(s);
        }

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
            eat("");
        }

        public String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                // TODO: handle exception
            }
            return null;
        }

        public boolean hasNext() {
            while (!st.hasMoreElements()) {
                String s = nextLine();
                if (s == null) {
                    return false;
                }
                eat(s);
            }
            return true;
        }

        public String nextToken() {
            hasNext();
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.valueOf(nextToken());
        }
    }
}