https://codeforces.com/contest/1733/problem/D2
Problem - D2 - Codeforces
codeforces.com
느리게 풂 + 튜토리얼이랑 내 풀이랑 달라서 기록
내 풀이
먼저 a랑 b에서 다른 인덱스를 배열 arr에 저장. arr.sz가 홀수면 불가능.
1) arr.sz = 2
arr[1] - arr[0] = 1 이면 min(x, y * 2)
아니면 min((arr[1] - arr[0]) * x, y)
2) arr.sz > 2
dp[cur][cnt] : cur ~ sz - 1 중에 인접한 원소 둘을 x만 이용해서 cnt / 2번 묶을때의 최소값.
dp[cur][cnt] = min(dp[cur + 1][cnt], dp[cur + 2][cnt - 2] + (arr[cur + 1] - arr[cur]) * x)
cur = sz - 1 또는 sz 일때 cnt가 0이면 0, 아니면 INF.
ans = min(dp[0][i] + (sz - i) / 2 * y) (0 <= i <= sz, i는 짝수)
(sz - cnt) / 2 개 쌍을 전부 y로 처리하는 건데 이 때 sz = 2이면 차이가 1일때 y한 번으로 처리가 불가능해서 sz = 2 를 예외처리했다.
튜토리얼 풀이
나중에 추가 예정