n길이의 수열을 k개의 그룹으로 나누고 각 그룹의 원소들을 or한 값을 모두 더한 값의 최대를 구하는문제.
어떻게 그룹을 나누어야하는지 계산해야한다.
이 상황을 dp로 표현할 수 있으며 아래처럼 opt를 구하는 문제로 변형시킬 수 있다.
dp[k][n]
--> n번째 원소까지 k개의 그룹으로 묶었을때 수열의 or점수의 최댓값.
cost[i][j]
--> i번째 부터 j번째까지 or한 값(하나의 그룹으로 묶었을때 그룹의 or)
dp[k][n] = dp[k-1][opt] + cost[opt+1][n]
--> (opt까지의 원소를 k-1로 묶은 최대 점수) + (opt+1부터 n까지 원소의 or값)
dp[k][n]을 최대로 만드는 opt를 opt(k, n)이라 하고 a가 양의 정수일때,
opt(k, n) <= opt(k, n + a)가 만족된다.
따라서 동적계획법을 분할정복으로 최적화 시킬 수 있다.
import java.io.*;
import java.util.*;
public class 수열의_OR_점수 {
static int N, K;
static long[] seq = new long[5001];
static long[][] dp = new long[5001][5001];//dp[k][n] : n번째 까지 k개의 그룹으로 나눴을때 점수의 최댓값
static long[][] cost = new long[5001][5001];//cost[i][j] : i번째 부터 j번째 까지 그룹으로 묶었을때 or점수
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++)
seq[i] = Long.parseLong(st.nextToken());
fillCost();
for(int i = 1; i <= N; i++)
dp[1][i] = cost[1][i];
for(int k = 2; k <= N; k++)
dncOpt(k, k, N, k - 1, N);
System.out.println(dp[K][N]);
}
//n이 최대 5000이기 때문에 시간복잡도 괜찮음
static void fillCost(){
for(int i = 1; i <= N; i++){
cost[i][i] = seq[i];
for(int j = i + 1; j <= N; j++) cost[i][j] = cost[i][j - 1] | seq[j];
}
}
static void dncOpt(int lev, int nLeft, int nRight, int optLeft, int optRight){
if(nLeft > nRight) return;
int mid = (nLeft + nRight) >> 1;
int opt = -1;
for(int o = optLeft; o <= Math.min(optRight, mid - 1); o++){
long val = dp[lev - 1][o] + cost[o+1][mid];
if(opt == -1 || val > dp[lev][mid]){
opt = o;
dp[lev][mid] = val;
}
}
dncOpt(lev, nLeft, mid - 1, optLeft, opt);
dncOpt(lev, mid + 1, nRight, opt, optRight);
}
}