[規格]11052-カード決済(java)

質問する
最近、ミンギュ家の近くではスターリンクから作られたPSカードの収集が流行している.
PSカードはPS分野の有名人の身分証明書です.カード1枚につき表示レベルの色が塗られており、以下の8種類があります.

伝説カード

赤カード

オレンジ色カード

パーソナルカード

ブルーカード

グリーンカード

グリーンカード

階調カード

カードはパッケージ形式でしか購入できません.パッケージの種類は1つのパッケージ、2つのパッケージ、...N個のカードを含むカードパックはN種類あります.
ミンギュ氏は、クレジットカードの数が少ないクレジットカードでも、価格が高ければ、高いレベルのクレジットカードがたくさんあると信じている.そのため、ミンギュはできるだけ多くのお金を払ってN枚のカードを買いたいと思っています.i枚のカードを含むパッケージの価格はPi元です.
例えば、P 1=1、P 2=5、P 3=6、P 4=7の4種類がある場合、ミンギュが4枚のクレジットカードを持つために支払った金額の最高値は10元である.2回に2つ入ったカードバッグを買えばいいです.
P 1=5、P 2=2、P 3=8、P 4=10の場合、1枚のカードが入ったカードパックを4回買うと20元になります.
最後に、P 1=3、P 2=5、P 3=15、P 4=16の場合、3つのカードパックと1つのカードパックを購入して18元を支払うのが最低価格です.
クレジットカードパックの価格を渡した場合、N枚のクレジットカードを購入するために、ミンギュが支払った金額の最低価格を求めるプログラムを作ってください.N枚以上のカードを買って、残りのカードを捨ててN枚にするのは不可能です.つまり、購入したカードパックに含まれるカード数の和はNに等しくなければならない.
入力
1行目はミンギュが購入するカードの個数Nを与える.(1 ≤ N ≤ 1,000)
2行目はP 1からPNまでPiの順に与えられる.(1 ≤ Pi ≤ 10,000)
しゅつりょく
1行目にミンギュがN枚のカードを持つために支払った金額の最高額がプリントアウトされる.
入力例

4
1 5 6 7

サンプル出力

10

コード#コード#

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];
        int[] dp = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = arr[i];
        }

        dp[1] = arr[1];
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] + dp[i - j]);
            }
        }

        bw.write(dp[N] + "\n");
        bw.close();
    }
}

整理する
抽出できる数を整理すると

1장 -> 1장
2장 -> 1장+1장 / 2장
3장 -> 1장+1장+1장 / 1장+2장 / 3장
4장 -> 1장+1장+1장+1장 / 1장+3장 / 2장+2장 / 4장
.
.

このようにして増加することがわかる.
したがって,最初にdp配列にパケット自体の値を設定し,forゲート内で金額の最値に更新すればよい.
2のfor文でj値をi/2に制限するのは、i/2を超えると1장+3장, 3장+1장という計算になるからである.