結果

問題 No.636 硬貨の枚数2
コンテスト
ユーザー ei1333333
提出日時 2018-01-19 22:06:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 710 bytes
コンパイル時間 2,445 ms
コンパイル使用メモリ 195,468 KB
最終ジャッジ日時 2025-01-05 07:42:53
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int INF = 1 << 29;

int arr[] = {0, 1, 2, 3, 4, 1, 2, 3, 4, 5};

string S;
int dp[10005][2];


int rec(int idx, bool pending)
{
  if(idx == -1) {
    if(pending != 0) return (INF);
    return (0);
  }
  if(~dp[idx][pending]) return (dp[idx][pending]);

  int ret = INF;
  for(int i = 0; i <= 9; i++) {
    auto need = i - pending < (S[idx] - '0');
    auto cost = arr[i] + arr[i - pending + (need ? 10 : 0) - (S[idx] - '0')];
    ret = min(ret, rec(idx - 1, need) + cost);
  }
  return (dp[idx][pending] = ret);
}

int main()
{

  cin >> S;
  S = "0" + S;
  memset(dp, -1, sizeof(dp));
  cout << rec(S.size() - 1, false) << endl;
}
0