結果
問題 | No.23 技の選択 |
ユーザー | ty70 |
提出日時 | 2015-06-22 02:15:11 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,619 bytes |
コンパイル時間 | 570 ms |
コンパイル使用メモリ | 89,188 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 16:47:16 |
合計ジャッジ時間 | 1,375 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <stack>#include <queue>#include <deque>#include <set>#include <map>#include <algorithm> // require sort next_permutation count __gcd reverse etc.#include <cstdlib> // require abs exit atof atoi#include <cstdio> // require scanf printf#include <functional>#include <numeric> // require accumulate#include <cmath> // require fabs#include <climits>#include <limits>#include <cfloat>#include <iomanip> // require setw#include <sstream> // require stringstream#include <cstring> // require memset#include <cctype> // require tolower, toupper#include <fstream> // require freopen#include <ctime> // require srand#define rep(i,n) for(int i=0;i<(n);i++)#define ALL(A) A.begin(), A.end()#define INF 1e100/*No.23 技の選択http://yukicoder.me/problems/33動的計画法dp[i]:= 現在の攻撃力が i のとき 通常攻撃または必殺技で攻撃した場合 最小の期待値dp[i] = min (dp[i-A] + 1, dp[i-D] + 3/2 );H ≦ i ≦ INF の範囲で res = min (res, dp[i] )*/using namespace std;typedef long long ll;typedef pair<int, int> P;const int MAX_H = 2*10005;double dp[MAX_H];int main(){rep (i, MAX_H ) dp[i] = INF;ios_base::sync_with_stdio(0);int H, A, D; cin >> H >> A >> D;dp[0] = 0.;for (int i = 0; i < MAX_H; i++ ){if (i - A >= 0 )dp[i] = min (dp[i], dp[i-A] + 1. );if (i - D >= 0 )dp[i] = min (dp[i], dp[i-D] + 3./2. );} // end ifdouble res = INF;for (int i = MAX_H-1; i >= H; i-- )res = min (res, dp[i] );printf ("%.5lf\n", res );return 0;}