[Java] Div2) C.Monsters and Spells - DP

https://codeforces.com/contest/1626/problem/C

Problem - C - Codeforces

각 몬스터에 대하여

등장 시간 k, 몬스터의 체력 h가 주어진다.

1초 전에 공격을 안했다면 1데미지의 공격이 가능하고

공격을 했다면 1초 전의 데미지가 x라고 하면 x+1의 공격이 가능하다.

즉, 선택지는 (공격 안하기, 1의 데미지 주기, x+1의 데미지 주기)

 

x데미지의 공격은 x마나를 사용하며, 체력이 h인 몹을 죽이려면 h이상의 공격이

몬스터 등장 시점에 사용되어야 한다.

필요한 최소 마나는 얼마인가?

 

case work해서 가장 나중에 등장하는 몬스터부터 거꾸로 탐색하여

세 가지 케이스로 나누어가며 동적 할당법으로 해결하였다.

정말 잘 만든 문제고 정말 잘 풀었다고 생각했는데 싱글벙글 풀고오니 unrated ㅋㅋ

코포 망해라

package contest.codeforce_0116;

import java.util.*;
import java.io.*;

public class q3{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);

    static int[] sec;
    static int[] health;
    static int[] pp;
    public static void main(String[] args){
        int T = fs.nextInt();
        for (int tt=0;tt<T;tt++){
            int n = fs.nextInt();
            sec = new int[n];
            health = new int[n];

            for (int i=0;i<n;i++) sec[i] = fs.nextInt();
            for (int i=0;i<n;i++) health[i] = fs.nextInt();

            pp = new int[]{sec[n-1]-health[n-1]+1, sec[n-1], health[n-1]};

            long sum = 0;
            for (int i=n-2;i>=0;i--){
                int left = sec[i] - health[i] + 1, right = sec[i], top = health[i];

                if (right < pp[0]){
                    sum += ((long)pp[2] + 1) * (long)pp[2] / 2;
                    pp = new int[]{left, right, top};
                }
                else if (left < pp[0]){
                    pp[0] = left;
                    pp[2] = top + (pp[1] - right);
                }
            }
            sum += ((long)pp[2] + 1) * (long)pp[2] / 2;

            pw.println(sum);
        }



        pw.close();
    }

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}