제출 #1160228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160228		siegeonsticks	Rabbit Carrot (LMIO19_triusis)	Java	0 / 100	60 ms	12100 KiB

triusis

import java.io.*;
import java.util.*;
public class triusis {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] h = new int[n];
        for (int i=0; i<n; i++) h[i] = Integer.parseInt(br.readLine());
        int res = solve(h, m);
        pw.println(res);
        pw.close();
        br.close();
    }
    private static int solve(int[] h, int m) {
        int n = h.length;
        int[] dp = new int[n];
        dp[0] = (h[0]<=m)?1:0;
        for (int i=1; i<n; i++) {
            dp[i] = (h[i]<=m*(i+1))?1:0;
            for (int j=i-1; j>=0; j--) {
                if (m*(i-j)<h[i]-h[j]&&h[i]>h[j]) break;
                if (h[i]<=h[j]+m*(i-j)&&dp[j]>0) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    if (dp[i]==dp[j]+1&&dp[j]==i-j) break;
                }
            }
        }
        int mxv = 0;
        for (int i=0; i<n; i++) mxv = Math.max(mxv, dp[i]);
        return n-mxv;
    }
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37