跳柱子

t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    li = list(map(int, input().split()))
    dp = [[False, 1] for _ in range(n)]
    dp[0][0] = True
    for i in range(1, n):
        flag = False
        max1 = 0
        for j in range(max(0, i - k), i):
            if dp[j][0] == False:
                continue
            elif li[j] >= li[i]:
                dp[i] = dp[j].copy()
                max1 = max(max1, dp[j][1])
                dp[i][1] = max1
                flag = True
            elif li[j] < li[i] and not flag and dp[j][1]:
                dp[i] = dp[j].copy()
                dp[i][1] = 0
    if dp[-1][0]:
        print('YES')
    else:
        print('NO')

#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAX_N 1000+100
int T;
int N, k;
int H[MAX_N];
int dp[MAX_N][3];


int main()
{

	scanf("%d", &T);
	while (T--)
	{
		memset(dp, 0, sizeof(dp));
		dp[0][1] = 1;
		dp[0][0] = 1;
		scanf("%d%d", &N, &k);
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &H[i]);
		}

		for (int i = 1; i < N; i++)
		{
			for (int j = 1; j <= k; j++)
			{
				if (i - j >= 0 && H[i] <= H[i-j]) {
					dp[i][0] |= dp[i - j][0];
					dp[i][1] |= dp[i - j][1];
				}

				dp[i][1] |= dp[i - j][0];
				
				
			}
		}

		if (dp[N - 1][0] || dp[N - 1][1])
			printf("YES\n");
		else
			printf("NO\n");
	}


	return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int T = 0;
	cin >> T;  //数据组数
	for (int i = 0; i < T; i++) {
		int n = 0, k = 0;
		cin >> n >> k;
		vector<int> heights(n, 0);
		for (int i = 0; i < n; i++) {
			cin >> heights[i];
		}
		vector<vector<bool>> dp(n, vector<bool>(2, false));
		dp[0][0] = true;  //第一个位置可以到达
		dp[0][1] = false;  //刚开始没有用超能力

		for (int j = 1; j < n; j++) {
			for (int i = 0; i < j; i++) {
				if (j - i > k) continue;  //不满足范围条件
				if (!dp[i][0]) continue;  //如果i不可达
				if (heights[i] >= heights[j] && dp[i][1] == false) {
					//最好情况，之前没有用过超能力，现在也不用
					dp[j][0] = true;
					dp[j][1] = false;
					break;  //避免最好情况被其他情况覆盖
				}
				else if (heights[i] >= heights[j] && dp[i][1] == true) {
					//之前用过超能力，现在不用
					dp[j][0] = true;
					dp[j][1] = true;   //之前用过了
				}
				else if (heights[i] < heights[j] && dp[i][1] == false) {
					//之前没有用过超能力，现在要用
					dp[j][0] = true;
					dp[j][1] = true;
				}
				else if (heights[i] < heights[j] && dp[i][1] == true) {
					//之前用过超能力，现在还要用，说明无法从该i到j，默认false
                    //直接改false会覆盖掉其他情况
					continue;
				}
			}
		}
		if (dp[n - 1][0] == true)
			cout << "YES" << endl;
		else 
			cout << "NO" << endl;
	}
}

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n = 0, k = 0;
        for (int i = 0; i < T; i++) {
            n = sc.nextInt();
            k = sc.nextInt();
            int[] nums = new int[n];
            for (int j = 0; j < n; j++)
                nums[j] = sc.nextInt();
            System.out.println(solution(n, k, nums));
        }
    }

    public static String solution(int n, int k, int[] nums) {
        int big = 1;
        int index = 0;
        while (index < nums.length - 1) {
            int tmp = index;
            int max = 0, max_index = index;
            for (int j = index + 1; j < index + 1 + k && j < nums.length; j++) {
                if (nums[j] < nums[index]) {
                    max_index = (max > nums[j]) ? max_index : j;
                    max = Math.max(nums[j], max);
                }
            }
            index = max_index;
            if (tmp == index && big > 0) {
                big--;
                max = 0;
                max_index = index;
                for (int j = index + 1; j < index + 1 + k && j < nums.length; j++) {
                    max_index = (max > nums[j])? max_index : j;
                    max = Math.max(nums[j], max);
                }
                index = max_index;
            }
            else if (tmp == index && big <= 0)
                return "NO";
        }
        return "YES";
    }
}

#include<iostream>
(720)#include<vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        vector<ll> h(n);
        for (ll i = 0; i < n; i++) {
            cin >> h[i];
        }
        vector<vector<int>> dp(n, vector<int>(n));
        vector<vector<int>> can_super(n, vector<int>(n));
        dp[0][0] = 1;
        int can_arrive = 0;
        can_super[0][0] = 1;
        for (ll i = 0; i < n; i++) {
            for (ll j = i; j <= min(i + k, n - 1); j++) {
                if (i == j && i != 0) {
                    for (int k = 0; k < i; k++) {
                        dp[i][j] = dp[i][j] | dp[k][j];
                        can_super[i][j] = can_super[i][j] | can_super[k][j];
                    }
                }
                if (h[j] > h[i] && can_super[i][i] == 1) {
                    dp[i][j] = 1;
                    can_super[i][j] = 0;
                }
                else if (h[j] <= h[i] && j!=i && dp[i][i] == 1) {
                    dp[i][j] = 1;
                    can_super[i][j] = can_super[i][i];
                }
            }
            can_arrive += dp[i][n - 1];
           /* if (can_arrive) {
                break;
            }*/
        }
        if (can_arrive) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
 
    }
}

import java.util.*;

public class Main{
    public static boolean solution(int[] nums, int k){
        int n = nums.length;
        boolean[][] dp = new boolean[n][2]; 
        dp[0][0] = true;
        dp[0][1] = true;
        for (int i = 1; i < n; i++){
            for (int j = 1; j <= k && i - j >= 0; j++){
                if (nums[i-j] >= nums[i]){
                    dp[i][0] |= dp[i-j][0]; 
                    dp[i][1] |= dp[i-j][1];
                }
                dp[i][1] |= dp[i-j][0]; 
            }
        }
        return dp[n-1][0] || dp[n-1][1];
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        for (int i = 0; i < T; i++){
            int n = input.nextInt();
            int k = input.nextInt();
            int[] nums = new int[n];
            for (int j = 0; j < n; j++){
                nums[j] = input.nextInt();
            }
            if(solution(nums,k)){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
}

function test (n, k, arrc) {
  let map = new Map(), arr = [0].concat(arrc)
  map[1] = true
  let flag = 0, last = -1
  for (let i = 2; i <= n; ++i) {
      for (let j = i - 1; j >= i - k && j >= 1; --j) {
          if (map[j] && arr[j] >= arr[i]) {
              map[i] = true
              if (i + k >= n) {
                  return true
              }
              flag = 0
              last = -1
              break
          } 
      }
      if (!map[i]) {
          if (!flag) {
              last = i
          }
          flag++
          if (flag === k) {
              break
          }
      }
  }
  if (last !== -1) {
      let max = arr[last], index = -1
      for (let i = last; i <= n && i <= last + k - 1; ++i) {
          if (max <= arr[i]) {
              max = arr[i]
              index = i
          }
      }
      if (index !== -1) {
          map[index] = true
          for (let i = index + 1; i <= n; ++i) {
              for (let j = i - 1; j >= i - k && j >= 1; --j) { 
                  if (map[j] && arr[j] >= arr[i]) {
                      map[i] = true
                      break
                  }
              }
          }
      }
  }
  return !!map[n]
}

var readline = require('readline');

var rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
});

let inputs = [], pr = 0
rl.on("line", line => {
  inputs.push(line.trim())
  let n = +inputs[0]
  if (inputs.length === (n*2+1)) {
    for(var h = 0; h < n; h++){
      var nu = inputs[h*2+1].split(' ').map(Number)[0]
      var k = inputs[h*2+1].split(' ').map(Number)[1]
      var arr = inputs[h*2+2].split(' ').map(Number)
      console.log(test(nu, k, arr) ? 'YES' : 'NO')
    }
  }
});

/*
  1
  10 5
  5 2 10 7 6 9 4 1 3 8
  No
  1
  10 4
  1 3 4 2 7 5 6 8 10 9
  1
  10 2 
  8 2 7 5 3 9 1 4 6 10
*/ 

public class Main_3 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        for (int i = 0; i < T; i++)  {
            int n = input.nextInt();
            int k = input.nextInt();
            int[] nums = new int[n];
            // 完成nums的赋值，得到nums数组
            for (int j = 0; j < n; j++) {
                nums[j] = input.nextInt();
            }
            // print output
            if (JumpPillar(n,k,nums)){
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    public static boolean JumpPillar(int n, int k, int[] nums) {
        // nums数组表示的是每个柱子的高度 柱子数为n 最大跳跃距离为k 超能跳跃只能使用1次
        // 由题知，柱子有n个，跳跃方式有2个，可由此确定状态
        // 状态 f[n][2]：能否通过正常跳跃或者超能跳跃到达n
        // f[n][0]：正常跳跃，f[n][1]：超能跳跃
        boolean[][] dp = new boolean[n][2];

        // initialization：在第一个柱子上不用跳直接可以到达
        dp[0][0] = dp[0][1] = true;

        /*
        最后可以到达柱子n ==> 最后一跳只有两种可能，普通跳跃和超能跳跃
        假设前面起跳位置为i，且最后一跳为超能跳跃，那么从第一个到第i个肯定全部是普通跳跃
        假设前面起跳位置为i，且最后一跳为普通跳跃，那么前面就存在一个超能跳跃的可能
        子问题：所以推广到任意一个j到i的位置，j可以使用两种到i的方式：普通或者超能
        Note：如果j采用普通到达的，那么后续它可以使用超能，但是如果j是采用超能到达的，后续就不能使用超能了
         */

        // from j to i
        for (int i = 0; i < n; i++) {
            // 对任意一个目标位置i，j的取值范围只能在[i-k, i-1]
            for (int j = i-1; j>=0 && j >= i-k; j--) {
                // j采用的是普通跳跃
                if (dp[j][0]) {
                    // from j to i：满足高度可以普通到达，不满足可以超能跳跃
                    if (nums[j] >= nums[i]) {
                        dp[i][0] = true;    // 普通
                    } else {
                        dp[i][1] = true;    // 超能
                    }
                }
                // j采用超能跳跃
                if (dp[j][1]) {
                    if (nums[j] >= nums[i]) {
                        dp[i][1] = true;
                    }
                }
            }
        }

        return dp[n-1][1];
    }
}

import java.util.*;

public class Main {
    public static void main(String [] args) {
                // 从前往后走，第一个柱子开始，统计后面k个柱子的最高柱子和小于等于当前柱子的最高柱子的坐标。
                // 在代码中分别为 m_i, 和 n_i
                // 如果没有小于等于当前柱子的，也就是没法走，尝试使用超能力，不能用了，就NO，能用就走到m_i
                // 如果有小于等于当前柱子的，走到 n_i
                // 总的来说是贪心的想法，如果能走，走能走的柱子中最高的；不能走，走包括不能走的最高的      
                Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int a = 0; a<t; a++) {
            int n = sc.nextInt(),k = sc.nextInt();
            int [] num = new int[n];
            for (int i=0; i<n; i++) num[i] = sc.nextInt();
            int cnt = 0,flag = 1;
            for (int i=0; i<n; ) {
                if (i == n-1) {
                    System.out.println("YES");
                    break;
                }
                int max = 0,nextMax = 0,m_i = -1,n_i = -1;
                for (int j=i+1; j<=i+k&&j<n ; j++) {
                    if (num[j]<=num[i] && num[j]>nextMax) {
                        nextMax = num[j];
                        n_i = j;
                    }
                    if (num[j]>max) {
                        max = num[j];
                        m_i = j;
                    }
                }
                if (nextMax == 0) {
                    if (flag == 1) {
                        flag = 0;
                        i = m_i;
                    }
                    else {
                        System.out.println("NO");
                        break;
                    }
                }
                else {
                    i = n_i;
                }
            }
        }
    }
}