13261번: 탈옥 - DP(DnC Opt)

 

DP - Divide and Conquer Optimization 기본 문제

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const ll INF = 1e18;
const int MAXL = 8001;
const int MAXG = 801;
int L, G;
ll psum[MAXL];
ll dp[MAXG][MAXL]; //dp[i][j] : i번째 간수까지 j번째 칸을 감시할 때 탈옥 위험도의 최솟값

//s, e : dp[i][m]를 최소로 만들어 주는 위치 opt의 범위
void solve(int s, int e, int l, int r, int i)
{
    if(l > r) return;
    
    int m = (l+r)/2;
    ll ans = INF;
    int opt = -1;
    
    //C[j][k] = (psum[j]-psum[k])*(j-k)
    //dp[i][j] = min(dp[i-1][k] + C[j][k]) (k < j)
    //C[j][k]는 사각 부등식을 만족하므로, DnC Opt를 이용해 O(GLlogL)로 문제를 해결할 수 있다.
    for(int j=s; j<=min(e, m-1); j++)
    {
        ll res = dp[i-1][j] + (psum[m]-psum[j])*(m-j);
        if(ans > res) ans = res, opt = j;
    }
    dp[i][m] = ans;
    
    //dp[i][m]에서 m이 작으면 dp 값을 최소로 만들어 주는 범위는 [s, opt],
    //m이 크면 dp 값을 최소로 만들어 주는 범위는 [opt, e]에 존재한다.
    solve(s, opt, l, m-1, i);
    solve(opt, e, m+1, r, i);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
    cin >> L >> G;
    G = min(G, L); //간수가 칸 수를 넘을 수는 없다.
    for(int i=1; i<=L; i++)
    {
        cin >> psum[i];
        psum[i] += psum[i-1];
    }
    
    for(int i=1; i<=L; i++) dp[1][i] = psum[i] * i; //전처리(기저 사례)
    //구해야 하는 범위 : i~L, 값이 될 수 있는 범위 : i-1~L-1
    for(int i=2; i<=G; i++) solve(i-1, L-1, i, L, i);
    cout << dp[G][L];
}