Patisserie | Aizu Online Judge

巡回セールスマン問題。

dp[すでに並べたケーキの集合][最後に置いたケーキ]としてメモ化再帰で解く。

グラフはG[ケーキv][ケーキu]として、ケーキvの次にケーキuを置く時、どれほど長さが増えるかで事前に作っておく。

同じサイズのケーキじゃない限り、ちょっとめりこむのでその数値を事前に計算しておく（シンプルな算数でOK）。

ケーキを一つも置いてない状態->新たにケーキを置く状態もノードに加えておく。

入力ケースが特殊なのでC++での方法が分からずちょっと手間取った。

double dp[10000][15];
double d[15][15];
double r[13];
int n;

double solve(int S, int v) {
    if (S == ((1<<n)-1)) {
        return dp[S][v] = 0;
    }
    if (dp[S][v] >= 0) return dp[S][v];

    double res = 1000*1000*1000;
    for (int i = 0; i < n; i++) {
        if (!((1 << i) & S)) {
            double ds = d[v][i];
            res = min(res, solve(S | (1 << i), i) + ds);
        }
    }

    return dp[S][v] = res;
}

int main() {
    while (1) {
        string s;
        getline(cin, s);
        stringstream ss(s);
        if (s == "") break;
        double m; ss >> m;
        n = 0;
        for (int i = 0; i < 13; i++) {
            ss >> r[i];
            if (!r[i]) break;
            n++;
        }
        for (int i = 0; i < 10000; i++)
            for (int j = 0; j < 15; j++)
                dp[i][j] = -1;
        for (int i = 0; i < 15; i++)
            for (int j = 0; j < 15; j++)
                d[i][j] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                if (r[i] == r[j]) {
                    d[i][j] = r[i]*2;
                    d[j][i] = r[i]*2;
                } else {
                    int a = abs(r[i] - r[j]);
                    int c = r[i] + r[j];
                    double b = sqrt(c*c-a*a);
                    d[i][j] = b + r[j] - r[i];
                    d[j][i] = b + r[i] - r[j];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            d[i][n] = 0;
            d[n][i] = r[i]*2;
        }
        if (solve(0, n) <= m) {
            cout << "OK" << endl;
        } else {
            cout << "NA" << endl;
        }
    }
    return 0;
}