[伯俊]9465:シール

質問する

問題を解く

例えば、cost[0][1]からの行き方を考えた.
cost[0][1]=50で行ける場所はcost[1][2]=50とcost[1][3].
dp[0][1] = Math.math(dp[1][2]、dp[1][3])+cost[0][1]で、どちらに行くかを決めることができます.
cost[0][3]に行くことを考えないのは、dp[1][2]に行くべき場所を選択する際に考えるからです.
これにより以下の法則が得られる.
dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + cost[0][j]
dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + cost[1][j]
Math.max(dp[0][n], dp[1][n])

コード#コード#

package DP;

import java.util.Scanner;

public class ANS9465 {

    static int dp[][], cost[][];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        //테스트 케이스
        int t = sc.nextInt();

        for(int i = 0 ; i < t ; i++){
            //테스트 케이스 별 n을 입력받는다.
            int n = sc.nextInt();

            //입력된 n에 따라 배열을 선언
            dp = new int[2][n+1];
            cost = new int[2][n+1];

            //2*n의 비용을 입력받는다.
            for(int j = 0 ; j < 2 ; j++){
                for(int k = 1 ; k <= n ; k++){
                    cost[j][k] = sc.nextInt();
                }
            }

            //dp초기화
            dp[0][1] = cost[0][1];
            dp[1][1] = cost[1][1];

	    //최댓값 구하기
            for(int m = 2 ; m <= n ; m++){
                dp[0][m] = Math.max(dp[1][m-1], dp[1][m-2]) + cost[0][m];
                dp[1][m] = Math.max(dp[0][m-1], dp[0][m-2]) + cost[1][m];
            }
		
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }


}

今はある程度、dpに自慢しているこの瞬間
2時間以来、タカは私を見て、自慢しないでと決心した今日
最初は最大の数から、探す方法を選んだが、そうではなかった.
今はもっと練習しなければなりませんね.