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());
        }
    }
}