티켓을 사다
문제
요즘 민규네 동네에서는 스타트링크 PS 카드 모으기가 유행이다.
PS 카드는 PS(Problem Solving) 필드에 유명인의 ID와 얼굴이 적힌 카드입니다. 각 카드는 등급을 나타내는 색상으로 칠해져 있으며 다음과 같은 8가지 유형이 있습니다.
- 레전드 카드
- 레드 카드
- 오렌지 카드
- 보라색 카드
- 파란색 카드
- 청록색 카드
- 그린 카드
- 그레이 카드
카드는 카드 팩 형태로만 구매할 수 있으며 다음과 같이 총 N 종류의 카드 팩이 있습니다. 예를 들어, 1-카드 팩, 2-카드 팩 및 N-카드 팩입니다.
Mingyu는 패키지에 적은 수의 카드가 포함되어 있어도 가격이 높으면 고품질 카드가 많다는 미신을 믿습니다. 그래서 민규는 최대한 많은 돈을 주고 N카드를 사려고 한다. i-card가 포함된 카드 팩의 가격은 Pi입니다.
예를 들어 카드팩의 종류가 P1=1, P2=5, P3=6, P4=7 4종류라면 민규가 최대 10개를 따야 4장을 얻을 수 있다. 카드 2개 묶음 2개 구입.
P1=5, P2=2, P3=8, P4=10의 경우 1장의 카드로 4장의 카드팩을 구매하는 데 드는 비용은 20원이며 이는 민규가 지불해야 하는 최대 금액이다.
마지막으로 P1=3, P2=5, P3=15, P4=16인 경우 최대값은 3장짜리 팩과 1장짜리 팩에 대해 18원입니다.
카드 한 벌의 가격이 주어졌을 때 민규가 N장의 카드를 사기 위해 지불해야 하는 최대 금액을 찾는 프로그램을 작성하세요. N개 이상의 카드를 구입하고 남은 카드를 버리고 N개를 얻는 것은 불가능합니다. 즉, 구입한 맵 팩에 포함된 맵의 개수의 합이 N이 되어야 합니다.
기입
민규가 사고 싶은 카드의 수 N은 첫 번째 줄에 명시되어 있습니다. (1 ≤ N ≤ 1,000)
두 번째 줄에는 Pi가 P1부터 PN까지 순서대로 주어집니다. (1 ≤ 파이 ≤ 10,000)
누르다
첫 번째 줄에는 민규가 N개의 카드를 가지기 위해 지불해야 하는 최대 금액을 입력합니다.
나의 접근
여러 개의 카드 팩을 선택할 때 n 번째 카드 팩에서 i 번째 카드가 선택된 경우를 고려하십시오. 이때 i의 범위는 1≤i≤n//2이다.
암호
n = int(input())
values = list(map(int,input().split()))
maxList = (0)*(n+1)
maxList(1) = values(0)
if n >=2 :
maxList(2) = max(maxList(1)*2,values(1))
for i in range(3,n+1):
maxList(i) = values(i-1)
div = i//2
for j in range(1,div+1):
maxList(i) = max(maxList(i),maxList(i-j)+maxList(j))
print(maxList(n))