[DP]문제#8.카드구매하기

 

11052번: 카드 구매하기 (acmicpc.net)

import java.util.*;
public class DP8 {
	
	static int N;
	static int[]d;
	static int[]p;
	
	public static void main(String[] args) {
		
	
		Scanner in=new Scanner(System.in);
		N=in.nextInt();
		d=new int[N+1];
		p=new int[N+1];
		
		for(int i=1;i<=N;i++) {
			p[i]=in.nextInt();
			d[i]=p[i];
		}
		d[1]=p[1];
		for(int i=2;i<=N;i++) {
			for(int j=1;j<=(i/2);j++) {
				d[i]=Math.max(d[j]+d[i-j],d[i]);
			}
		}
		
	System.out.println(d[N]);
	}
}