백준 13262번 수열의 OR 점수

문제 요약

크기가 N인 수열을 연속된 구간 K개로 나누려고 한다. 하나의 구간의 점수는 해당 구간에 속한 정수들의 OR값이다.

구간들의 점수의 합을 최대화하시오.

N, K는 최대 5000이다.

풀이

먼저 $C(i,j)$를 $a_i, a_{i+1}, \cdots , a_j$까지의 수들을 OR한 값이라고 하자.

그러면 다음과 같은 dp식이 나온다
$$
\begin{gather}
dp(i,j) = \text{수열을 1부터 j까지 i개의 구간으로 나눴을 때의 최댓값} \\
dp(i,j) = \underset{k<j}{max}(dp(i-1, k) + C(k+1, j))
\end{gather}
$$
C(i, j)랑 C(i,j+1)을 비교해보면 후자가 무조건 크거나 같다는 것을 알 수 있다.

$dp(i, j)$의 점화식에서 $dp(i,j)$의 값을 최대로 만들어주는 $k$의 값을 $opt_j$라고 하자.

$j < j'$일 때, 위 C의 특성때문에 $opt_j \le opt_{j'}$라는 것을 알 수 있다. 따라서, 분할정복 최적화를 적용할 수 있으며 $O(NKlogN)$에 문제가 해결 가능하다.

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

ll C[5005][5005];
ll arr[5005];
ll dp[5005][5005];
int N, K;

void solve(int lev, int s, int e, int optl, int optr) {
    if(s > e) return ;
    int mid = (s+e) >> 1;
    ll &ans = dp[lev][mid];
    ans = dp[lev-1][optl] + C[optl+1][mid];
    int opt = optl;
    for(int i=optl;i<min(mid, optr);++i) {
        ll val = dp[lev-1][i] + C[i+1][mid];
        if(opt == -1 || ans < val) {
            opt = i; ans = val;
        }
    }
    solve(lev, s, mid-1, optl, opt+1);
    solve(lev, mid+1, e, opt, optr);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K;
    for(int i=1;i<=N;++i) cin >> arr[i];
    for(int i=1;i<=N;++i) for(int j=i;j<=N;++j) C[i][j] = C[i][j-1] | arr[j];
    for(int i=1;i<=N;++i) dp[1][i] = C[1][i];
    for(int i=2;i<=K;++i) solve(i, i, N, i-1, N);
    cout << dp[K][N] << '\n';
    return 0;
}