BOJ 20938 반짝반짝

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

20938번: 반짝반짝

 

dp를 두 번 돌리면 풀리는 문제입니다.

 

$\mathcal{O}(N^2)$에 임의의 $l$과 $r$에 대해서 $l$부터 $r$까지의 조각의 기댓값을 구할 수 있습니다. 이 때 나이브하게 짜면 $\mathcal{O}(N^3)$의 시간이 걸리므로 메모이제이션을 통해 최적화를 해줘야 합니다.

 

이후 주어진 전구를 어떻게 $k$개 이하의 조각으로 나눠야 최적인지 찾으면 됩니다. 이는 $\mathcal{O}(KN^2)$에 해결할 수 있는데, $memo[x][cnt]$를 $x$번째까지의 전구를 $cnt$개의 조각으로 나눴을 때의 최대 기댓값으로 하면 dp를 통해 구할 수 있습니다.

 

출력할 때 소수점 자릿수를 설정하지 않아서 틀렸습니다. 슬퍼요.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, k;
double prob[2550], memoProb[2550][2550], memo[2550][11];

double calcProb(int s, int e) {
  if (memoProb[s][e] >= -0.01) return memoProb[s][e];
  if (s == e) return memoProb[s][e] = prob[s];
  return memoProb[s][e] = prob[s] + prob[s] * calcProb(s + 1, e);
}

double dp(int x, int cnt) {
  if (x + 1 < cnt) return -9999;
  if (cnt == 1) return memoProb[0][x];
  if (memo[x][cnt] >= -0.01) return memo[x][cnt];

  double ret = 0;
  for (int i = 1; i <= x; i++) ret = max(ret, dp(i - 1, cnt - 1) + memoProb[i][x]);

  return memo[x][cnt] = ret;
}

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
      cin >> prob[i];
      prob[i] = 1 - prob[i];
    }

    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) memoProb[i][j] = -1;
    for (int i = 0; i < n; i++) for (int j = i; j < n; j++) calcProb(i, j);

    for (int i = 0; i < n; i++) for (int j = 0; j <= k; j++) memo[i][j] = -9999;

    double ans = 0;
    for (int i = 1; i <= k; i++) ans = max(ans, dp(n - 1, k));

    cout << fixed << setprecision(15);
    cout << ans << endl;
  }

  return 0;
}