結果
問題 |
No.636 硬貨の枚数2
|
ユーザー |
![]() |
提出日時 | 2018-01-19 22:25:45 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 976 bytes |
コンパイル時間 | 629 ms |
コンパイル使用メモリ | 81,244 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 12:37:16 |
合計ジャッジ時間 | 2,231 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 65 |
ソースコード
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <string> #include <iomanip> #include <algorithm> #include <cmath> #include <stdio.h> using namespace std; #define int long long int MOD = 1000000007; int dp[10005][2]; int a1[11] = { 0,1,2,3,2,1,2,3,3,2,1 }; //int a2[11] = { 0,1,2,3,4,1,2,3,4,5,1 }; signed main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; while (S.back() == '0') { S.pop_back(); } int N = S.size(); dp[0][0] = 0; dp[0][1] = 1; for (int i = 0; i < N; i++) { dp[i + 1][0] = dp[i][0] + a1[S[i] - '0']; dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + a1[10 - (S[i] - '0')]); dp[i + 1][1] = dp[i][0] + a1[1 + (S[i] - '0')]; dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + a1[9 - (S[i] - '0')]); } /*for (int i = 0; i <= N; i++) { cerr << dp[i][0] << " "; } cerr << endl; for (int i = 0; i <= N; i++) { cerr << dp[i][1] << " "; } cerr << endl;*/ cout << dp[N][0] << endl; }