Patisserie | Aizu Online Judge
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; }