[BOJ 4008] 특공대
DP[i] = 1 ~ i 병사들로 얻을 수 있는 조정된 전투력의 최댓값 위와 같은 간단한 DP를 구하면 된다. SUM[i] = X[1]+X[2]+...+X[i] 로 미리 sum 배열을 구해 놓으면 SUM[i] - SUM[j] = X[j+1]+X[j+2]+...+X[i] 가 성립하므로 아래와 같이 DP[i]를 구할 수 있다. 이 식을 전개하여 컨벡스 헐 트릭을 사용할 수 있게 i 와 관련된 함수( = SUM[i]가 곱해진 항) , j와 관련된 함수, 상수를 나누면 위와 같이 된다. 이제 A[i] = SUM[i], B[j] = -2*a*sum[j]+b, C[j] = DP[j]-b*sum[j]+a*sum[j]^2, D[i] = a*sum[i]^2+c 로 대응시킬 수 있다. min 함수가 아닌 max 함수이지만..
문제 풀이
2017. 10. 31. 17:32