TopCoder SRM 314 DIV 1 Medium 練習

問題

整数が幾つかあたえられて、ここから三つとって、それを三辺の長さとする三角形をたくさん作る。

合計の面積が最大になるような三角形の作り方をしたとき、面積はいくらか。

解

整数の数の最大が16。これはintエンコードでメモ化しろって言ってるようなもんじゃんｗｗ←気付くのに10分かかった

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class GrasslandFencer {
    private double area(int a, int b, int c)
    {
        double p = (a + b + c) / 2.0;
        return Math.Sqrt(p * (p - a) * (p - b) * (p - c));
    }

    private bool valid(int a, int b, int c)
    {
        return a + b > c && b + c > a && a + c > b;
    }

    List<int> fences;
    bool[] memop;
    double[] memo;
    int N;
    public double maximalFencedArea(int[] fences_) {
        fences = new List<int>(fences_);
        N = fences.Count;
        memo = new double[1 << 16];
        memop = new bool[1 << 16];

        return srch((1 << N) - 1);
    }

    private double srch(int p)
    {
        if (memop[p])
            return memo[p];

        memop[p] = true;
        if (p == 0)
            return memo[p] = 0.0;

        memo[p] = 0.0;
        for(int i = 0; i < N; ++i) if((p & (1 << i)) != 0)
            for(int j = i+1; j<N; ++j) if((p & (1 << j)) != 0)
                for (int k = j + 1; k < N; ++k) if ((p & (1 << k)) != 0)
                        if (valid(fences[i], fences[j], fences[k]))
                        {
                            memo[p] = Math.Max(memo[p], srch(p ^ (1 << i) ^ (1 << j) ^ (1 << k)) + area(fences[i], fences[j], fences[k]));
                        }
        return memo[p];
    }
}