CodeForce 1760D Challenging Valleys

[Woodyiiiiiii]

这道题使用的方法是状态机。

1. 观察，发现只有^形或者之后的变化是不符合条件的
2. 将其命名为一个状态，只要不是该状态的都符合条件
3. 分状态

还不是很懂状态机类型的题目，还需要多做题。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T -- > 0){
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
            System.out.println(checkV(arr) ? "YES" : "NO");
        }
    }

    public static boolean checkV(int[] arr) {
        int state = 0;
        // 0 - init, 1 - up, 2 - down, 3 - up and down

        for (int i = 1; i < arr.length; ++i) {
            // trend not change
            if (arr[i] == arr[i - 1]) {
                continue;
            }

            if (arr[i] > arr[i - 1]) {
                state = 1;
            } else {
                if (state == 0) {
                    state = 2;
                } else if (state == 1) {
                    state = 3;
                    break;
                }
            }
        }

        return state != 3;
    }



}

---

• https://codeforces.com/problemset/problem/1760/D