[伯俊]No 2156-ワイン試飲(JAVA)




3つのワインを連続的に飲めない条件はhttps://www.acmicpc.net/problem/2579と似ている.私はその質問に答えている間に知らなかったので、放っておいて、ついでにこのタイプの質問を知りたいのでブログ記事を書きました.
まず問題で与えられた条件.
  • できるだけワインをたくさん飲みます.
  • に続く3つのワインは飲めません.
  • ワインを3つ続けて飲めません。


    つまり.
    連続
  • 0個->可能
  • 連続
  • 1個->可能
  • 連続
  • 2個->可能
  • 同じ言葉.したがって、max[i]をi号で飲めるブドウ酒の酒量の最高値と呼び、wine[i]をi号に含まれるブドウ酒の酒量と呼ぶと、max[i] = max[i-1]/0連続?Xmax[i] = wine[i] + max[i-2]/1連続?XOmax[i] = wine[i] + wine[i-1] + max[i-3]/2個の連続XOO
    いいですよ.
    0個連続で、i-1i-2でワインを飲んでも飲まなくても.したがって、max[i]はmax[i-1]の値に等しい.
    1個連続の場合、i-1は必ずしも飲む必要はありません.しかしi-2は関係ありません.したがって、max[i]は現在連続した値であるため、wine[i]にmax[i-2]を加算する.
    2つ連続の場合は必ずi-1、必ずしもi-2を飲む必要はありません.したがって、max[i]=wine[i]+wine[i-1]+max[i-3]となる.

    ✔この3つの条件の中で最大の値は[i]を占めます。


    また、イグニッション式ではi-3に近いので、ループ文の前に初期値を設定!
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class No2156_포도주시식 {
        static int[] wine = new int[10001];
        static int[] max = new int[10001];
        static int n;
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
            for (int i=1;i<=n;i++) {
                wine[i]=Integer.parseInt(br.readLine());
            }
    
            max[1]=wine[1];
            max[2]=wine[1]+wine[2];
            max[3]=Math.max(max[2],Math.max(wine[3]+wine[1],wine[2]+wine[3]));//초기값 세팅
          
    
            for (int i=4;i<=n;i++) {
                max[i]=Math.max(Math.max(max[i-1],wine[i]+max[i-2]),wine[i]+wine[i-1]+max[i-3]);
            }
    
            System.out.println(max[n]);
        }
    
    }
    

    に感銘を与える


    このように,dp問題に'몇개 이상 연속하지 못하는'の条件がある場合,この方法で近づくことが分かった.
    明日は階段を登る問題も解決しなければなりません.頑張ってください.