結果
問題 | No.463 魔法使いのすごろく🎲 |
ユーザー |
|
提出日時 | 2016-12-14 03:45:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,765 bytes |
コンパイル時間 | 1,662 ms |
コンパイル使用メモリ | 174,452 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-30 07:04:25 |
合計ジャッジ時間 | 2,882 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<vector<double>> reduce(vector<vector<double>> a) { int h = a.size(); int w = a[0].size(); int r = 0; for (int j = 0; j < w && r < h; j++) { int p = r; for (int i = r + 1; i < h; i++) { if (abs(a[i][j]) > abs(a[p][j])) { p = i; } } swap(a[p], a[r]); if (abs(a[r][j]) < 1e-8) { continue; } for (int ii = 0; ii < h; ii++) { if (ii != r) { double q = a[ii][j] / a[r][j]; for (int jj = 0; jj < w; jj++) { a[ii][jj] -= q * a[r][jj]; } } } double q = a[r][j]; for (int jj = 0; jj < w; jj++) { a[r][jj] /= q; } r++; } assert(r == h); return a; } int main() { int n, m; cin >> n >> m; vector<double> c(n); for (int i = 1; i < n - 1; i++) { cin >> c[i]; } vector<vector<double>> a(n - 1, vector<double>(n)); for (int i = 0; i < n - 1; i++) { a[i][i] = 1; for (int j = 1; j <= m; j++) { int ii = i + j; if (ii >= n - 1) { ii = 2 * (n - 1) - ii; } if (ii < n - 1) { a[i][ii] -= 1.0 / m; } a[i][n - 1] += c[ii] / m; } } a = reduce(a); vector<double> dp(n); for (int i = n - 2 - m; i >= 0; i--) { double mini = 1e100; for (int j = 1; j <= m; j++) { dp[i] += (dp[i + j] + c[i + j]) / m; mini = min(mini, a[i + j][n - 1] + c[i + j]); } dp[i] = min(dp[i], mini); } printf("%.20f\n", dp[0]); }