BOJ 10067 - 수열 나누기

문제 링크 : https://www.acmicpc.net/problem/10067

문제 소개

길이 n의 수열을 k번 자른다. 자를 때 마다, 자른 후 양쪽 수열의 값의 각각의 합을 곱한 것만큼 점수를 얻는다. 이때 얻을 수 있는 최대 점수와 자르는 방법을 구하시오.

문제 풀이

우리는 이 문제를 최종 시점관점에서 보면서 점수에 어떤 값을 이 추가되었는지를 살펴보아야 한다. 
(a,b,c,d)를 (a,b),(c,d)로 잘랐다고 하자. 이러면 우리는 (a+b)*(c+d)의 점수를 얻게 된다. 이를 다른 식으로 풀어쓰면 ac+ad+bc+bd 만큼의 점수를 얻게 된다는 것이다. 이는 서로 다른 그룹에 속하는 임의의 두 값을 곱해서 더한 값이다. 결국 그전에 어떤 순서로 어떻게 잘랐건 간에, 마지막에 다른 그룹에 있는 임의의 두 숫자를 곱한 값을 싹다 더하면 점수가 나오게 된다,

DP[i][j]=i번째 숫자까지, j개의 구간을 사용하여 얻을 수 있는 최댓값이라고 정의하자.
그러면 아래와 같은 식이 나오게 된다. 
$DP[i][k]=\underset{j<i}{min}(sum(1\sim j)*sum({j+1}\sim i)+DP[j][k-1])$ 
이때 다른 문제에서도 그랬듯이 구간 합은 prefix sum으로 바꿈으로써 등식을 더 예쁘게 수정이 가능하다.
$DP[i][k]=\underset{j<i}{min}(pre[j]\times (pre[i]-pre[j])+DP[j][k-1])$ 

이 식은 CHT를 사용해서 풀 수 있고, 역추적까지 가능하다. 따라서 CHT를 이용하면 문제를 해결 할 수 있다.

코딩

- 코딩하는 과정에서 메모리가 넘치기 때문에 토글링을 해주었다.
- 들어오는 x값이 계속 증가하기 때문에 O(N) CHT를 사용하였다.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pii pair<ll,ll>
struct lin{
    ll a,b;
};
struct CHT{
    ll s=0,e=0;
    ll idx[101010];
    lin deq[101010];
    double cross(int a, int b) {
        return 1.0 * (deq[a].b - deq[b].b) / (deq[b].a - deq[a].a);
    }
    void insert(lin v,ll lidx){
        deq[e] = v;
        idx[e] = lidx;
        while(s<e&&(deq[e].a==deq[e-1].a)&&deq[e-1].b<=deq[e-1].b){
            deq[e-1] = deq[e];
            idx[e-1] = idx[e];
            e--;
        }
        while(s+1<e && cross(e - 2, e - 1) > cross(e - 1, e)){
            deq[e-1] = deq[e];
            idx[e-1] = idx[e];
            e--;
        }
        e++;
    }
    pii query(ll x){ 
        while(s+1<e && deq[s+1].b - deq[s].b >= x * (deq[s].a - deq[s+1].a))
            s++;
        return pii(deq[s].a*x+deq[s].b,idx[s]);
    }
    void re(){
        s=0;
        e=0;
    }
 
}cht;
 
ll pre[101010];
ll dp[2][101010];
ll arr[101010];
int com[202][101010];
int ans[202];
 
int main(){
    ll i,j,k,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&arr[i]);
        pre[i]=arr[i]+pre[i-1];
    }
    lin l;
    for(i=1;i<=m;i++){
        cht.re();
        for(j=1;j<=n;j++)
            dp[0][j]=dp[1][j];
        for(j=i;j<=n;j++){
            dp[1][j]=cht.query(pre[j]).first;
            com[i][j]=(int)cht.query(pre[j]).second;
            l.a = pre[j];
            l.b = -pre[j]*pre[j]+dp[0][j];
            cht.insert(l,j);
        }
    }
    printf("%lld\n",dp[1][n]);
    for(i=m;i>=1;i--){
        ans[i]=com[i][n];
        n=com[i][n];
    }
    for(i=1;i<=m;i++)
        printf("%d ",ans[i]);
}