백준 10067 (C++) 수열 나누기

최초 업로드: 2025-11-09 13:13:02

최근 수정 시간: 2025-11-09 14:00:29

게시자: rlatjwls3333

카테고리: 백준

# [Diamond IV] 수열 나누기

[문제 링크](https://www.acmicpc.net/problem/10067)

## 문제 설명

은기는 음이 아닌 정수 n개로 이루어진 수열을 이용해 시간을 때우고 있다. 은기는 수열을 총 k+1개로 나누어야 하고, 각 부분은 비어있지 않아야 한다. 수열을 k+1개로 나누러면, 아래와 같은 과정을 k번 반복해야 한다.

위의 과정을 할 때마다 얻게되는 점수는 새로 나누어진 각 부분에 들어있는 원소의 합을 곱한 것이다. 위의 과정을 k번 반복하면서 은기가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 두 정수 n과 k가 주어진다. (2 ≤ n ≤ 100,000, 1 ≤ k ≤ min(n-1, 200)) 둘째 줄에는 수열을 나타내는 음이 아닌 정수 n개 a1, a2, ..., an이 주어진다. (0 ≤ ai ≤ 104)

## 출력

첫째 줄에 얻을 수 있는 가장 큰 점수를 출력한다. 둘째 줄에는 그러한 점수를 얻기 위해 몇 번째 원소 다음에 수열을 나누어야 하는지 순서대로 출력한다. 가능한 답이 여러개라면, 아무거나 출력한다.

## 풀이
K등분으로 나눈 덩어리를 $S_1$ $S_2$ ... $S_{k+1}$이라 하면 총 점수는 $S_1(S_2 + ... + S_{k+1}) + S_2(S_3 + ... + S_{k+1}) + ...$점이다.

따라서 $dp[i][j]$를 j까지의 원소들을 i번 분할했을 때의 최대 점수로 둔다면 $dp[i][j] = max(dp[i-1][k] + preSum[k](preSum[j] - preSum[k]))$라는 식이 세워진다. 이를 정리하면 $dp[i][j] = dp[i-1][k] - preSum[k]^2 + preSum[k]preSum[j]$로 나타낼 수 있고 preSum[j]를 x로 두면 CHT가 가능하다. 메모리 제한만 추가적으로 신경써주면 풀 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 100'001;

// dp[i][j] : j까지 총 i번 잘랐을 때 최대 점수
int trace[201][MAX];
ll preSum[MAX], dp[2][MAX];

struct element {
    ll a, b, idx;
    double x=-1e150;
};

double meetX(element a, element b) {
    return (double)(a.b-b.b)/(b.a-a.a);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, k; cin >> n >> k;
 for(int i=1;i<=n;i++) {
 cin >> preSum[i];
 preSum[i] += preSum[i-1];
 }

for(int i=1;i<=k;i++) {
 vector<element> stk;
 for(int j=i;j<=n;j++) {
 ll x = preSum[j];
 element cur = {preSum[j], dp[(i-1)%2][j]-preSum[j]*preSum[j], j};
 while(!stk.empty()) {
 if(cur.a==stk.back().a) {
 cur.b = max(cur.b, stk.back().b);
 } else {
 cur.x = meetX(cur, stk.back());
 if(cur.x>stk.back().x) break;
 }
 stk.pop_back();
 }
 stk.push_back(cur);

int left=0, right=stk.size()-1;
 while(left<right) {
 int mid = left+right+1>>1;
 if(x<stk[mid].x) right=mid-1;
 else left=mid;
 }
 dp[i%2][j] = stk[left].a*x+stk[left].b;
 trace[i][j] = stk[left].idx;
 }
 }
 cout << dp[k%2][n] << '\n';
 while(k) {
 n = (trace[k][n]==n ? n-1 : trace[k][n]);
 cout << n << ' ';
 k--;
 }
}
```