SRM314 D1M-D2H GrasslandFencer

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.

辺が$n$本与えられるので，その辺の中で三角形を作り，その面積の合計を最大化する．辺の最大数が$16$と小さいので，辺を使ったか使っていないかの情報をbitで持つ．

$$ dp[S] := 状態Sでの面積の最大値 $$

として動的計画法．現在見ている状態から，三角形を全探索し，まだ使っていない辺で構成されている場合にchmaxをする．三角形の条件，面積の求め方は問題ページに書いてあって優しさを感じた．

Code

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<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

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

double f(double a, double b, double c) {
  double p = (a + b + c) / 2;
  return sqrt(p * (p - a) * (p - b) * (p - c));
}

double dp[1 << 20];

class GrasslandFencer {
  public:
  double maximalFencedArea(vector <int> fences) {
      int n = fences.size();
      sort(fences.begin(), fences.end());

      memset(dp, 0, sizeof(dp));

      rep(bit, 1<<n) {
          rep(i, n) {
              REP(j, i+1, n) {
                  REP(k, j+1, n) {
                      double a = fences[i];
                      double b = fences[j];
                      double c = fences[k];

                      if(a + b <= c) continue;

                      int state = 0;
                      state |= (1 << i);
                      state |= (1 << j);
                      state |= (1 << k);

                      if(bit & state) continue;

                      dp[bit | state] = max(dp[bit | state], dp[bit] + f(a, b, c));
                  }
              }
          }
      }

      double ans = 0;
      rep(bit, 1<<n) {
          ans = max(ans, dp[bit]);
      }

      return ans;
  }
};
Oct 6th, 2016
bitdp, srm, topcoder, 動的計画法