[BOJ 13261] 탈옥

https://www.acmicpc.net/problem/13261

13261번: 탈옥

Tag : dnc opt

 

 

문제요약

간수 한명이 구간 \([l,r]\)을 관리할 때 이 위험도는 구간의 탈옥력 \(C_i\)들의 합과 구간의 크기인 \(r-l+1\)의 곱으로 정의된다.

간수가 G명일 때 \([1,L]\)의 위험도의 합을 최소화하는 것이 목표다. 

 

풀이

직관적으로 떠올릴 수 있는 dp의 정의는 다음과 같다.

\(dp_{i,j}:=i\)명의 간수가 \([1:j]\)의 감옥을 관리할 때 최소 위험도

이 식을 그대로 짜게된다면 \(O(GL^2)\)으로 시간초과가 날 것이다.

 

\(dp_{i,j}=min(dp_{i-1,k}+C(k+1,j))\)에서 \(dp_{i,j}\)를 최소로 만드는 k를 \(P(i)\)라 하자.

 

monge array : a<=b<=c<=d 이면 \(C(a,d)+C(b,c) \geq C(a,c)+C(b,d)\)

\(C(l,r)\)은 monge array의 성질을 만족하기 때문에 dnc opt를 사용해 \(O(GLlogL)\)시간에 해결할 수 있다.

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

ll L,G;
ll v[8080];
ll sum[8080];
ll P[808][8080];
ll dp[808][8080];

ll C(int l,int r){return (r-l+1)*(sum[r]-sum[l-1]);}

void dnc(int idx,int s,int e,int l,int r){
    if(s>e)return;
    int m=(s+e)/2;
    dp[idx][m]=0x3f3f3f3f3f3f3f3f;
    for(int i=l;i<=r;i++){
        if(dp[idx][m]>dp[idx-1][i]+C(i+1,m)){
            dp[idx][m]=dp[idx-1][i]+C(i+1,m);
            P[idx][m]=i;
        }
    }
    dnc(idx,s,m-1,l,P[idx][m]);
    dnc(idx,m+1,e,P[idx][m],r);
}

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    L=f();G=f();
    for(int i=1;i<=L;i++)v[i]=f();
    for(int i=1;i<=L;i++)sum[i]=sum[i-1]+v[i];
    for(int i=1;i<=L;i++)dp[1][i]=C(1,i);
    for(int i=2;i<=G;i++)dnc(i,1,L,1,L);
    cout<<dp[G][L]<<endl;
}