[イコール]アリ戦士

質問する
アリ戦士は不足した食糧を補うためにバッタ村の穀倉を襲撃する準備をしている.バッタ村にはいくつかの穀倉があり、穀倉は直線である.各穀倉には一定数の食糧が貯蔵されており、アリ戦士は選択的に穀倉を略奪し、食糧を奪う.この時、バッタ偵察兵たちは一直線上に存在する穀倉の中で、隣接する穀倉が攻撃を受けると、すぐに発見される.だからアリ戦士は偵察兵に発見されないように食糧倉庫を略奪した. 少なくとも1つ以上の穀倉を略奪しなければならない. 例えば、4つの穀倉があると仮定すると、以下のようになります.

{1, 3, 1, 5}

この時、アリ戦士は2番目の穀倉と4番目の穀倉を選んだ時、最大8つの食糧を奪うことができる.蟻の戦士が穀倉でこんなにまっすぐだったとき
アリ戦士のためにプログラムを作って、N個の穀倉に関する情報を得たとき、得られる食糧の最高価格.
入力

行目は食糧倉庫の個数Nを与えた.(3<=N<=100)

の2行目は空白に分けられ、各穀倉に貯蔵された食糧の数はKである.(0<=K<=1,000)

しゅつりょく

行目にアリ戦士が得ることができる食糧の最高価格を輸出した.

に答える
連続して2つの格を選ぶことができないことに注意して、点火式を考えなければなりません.これはアリ戦士が得られる食糧を求める最高価格の問題だからだ.
dp[i]=max(dp[i−2]+arr[i],dp[i−1])dp[i]=max(dp[i-2]+arr[i], dp[i-1])dp[i]=max(dp[i−2]+arr[i],dp[i−1])
このように儀式を立てなければならない.
すなわち、i位置の食糧を食べると、最も隣接する食糧がi-2になるので、i-2の食糧の最高価格(dp[i-2])と現在の食糧(arr[i])を加えることができます.このような状況をi位置の食糧を食べず、i−1を食べた時の食糧の最低価格に比べて、より大きな価格をdp[i]に貯蔵した.
このとき、現在位置2格子以外の位置の値が計算に用いられるため、dp[0]とdp[1]はメイン関数で初期化される.dp[0]は一番前の食べ物しかないのでarr[0]で初期化でき、dp[1]ならarr[0]とarr[1]のより大きな値で初期化できます.
コード#コード#

package Ch8_dp;

import java.util.*;
import java.io.*;
public class 실전3_개미전사 {

	static int[] arr;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		arr=new int[N];
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp=new int[N];
		dp[0]=arr[0];
		dp[1]=Math.max(arr[0], arr[1]);
		
		System.out.println(solution());
	}

	static int solution() {
		for(int i=2;i<dp.length;i++) {
			dp[i]=Math.max(dp[i-1], arr[i]+dp[i-2]);
		}
		
		return dp[dp.length-1];
	}
}