SRM335 D2H MinimumVariancePartition

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

数列が与えられる．この数列を$k$個の数列に分け，それぞれの数列の分散の和を最小化したい．まず初めに$[i, j)$の分散を全て計算しておく．

$$ dp[i][j] := i番目までをj個に分けた時の分散の和の最小値 $$

として動的計画法．$j$番目まで見て$k+1$個に分ける時は，$[0, i)$と$[i, j)$に分けて$dp[i][k]$と$[i, j)$の分散の和を候補としてminを取っていく．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class MinimumVariancePartition {
  public:
  double minDev(vector <int> mixedSamples, int K) {
      vector<int> v = mixedSamples;
      sort(v.begin(), v.end());

      double dp[55][55];
      rep(i, 55) rep(j, 55) dp[i][j] = INF;
      dp[0][0] = 0;

      double var[55][55];
      memset(var, 0, sizeof(var));
      rep(i, v.size()) {
          REP(j, i+1, v.size()+1) {
              double mean = 0;
              REP(k, i, j) {
                  mean += v[k];
              }
              mean /= (j - i);

              REP(k, i, j) {
                  var[i][j] += (v[k] - mean) * (v[k] - mean);
              }
              var[i][j] /= (j - i);
          }
      }

      rep(i, v.size()) {
          REP(j, i+1, v.size()+1) {
              rep(k, K) {
                  dp[j][k+1] = min(dp[j][k+1], dp[i][k] + var[i][j]);
              }
          }
      }

      return dp[v.size()][K];
  }
};
Feb 5th, 2017
srm, topcoder, 動的計画法, 区間dp