2020年3月21日Benelux Algorithm Programming Contest 2019

E. Efficient Exchange

題意：這一題的題意簡單；簡單來說就是A、B有1元10元、100元、1000元。。。。等等10的整次冪的票額的紙幣，現在B付錢給A，問當中涉及錢的張數最少是多少可以把錢付清。

題解：這一題官方題解給的是DP+遞歸，自己看了半天，代碼中的註釋給出了自己的理解，

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 using namespace std;
 5 int dp[10005][2];//dp[i][j]:當為dp[i][0]表示推到數據的第 i 位數，同時表示在這一位最低的或貨幣值
 6                  //             dp[i][1]表示推到數據的第 i 位數，同時表示這一位數據的最低值+1所表示的貨幣值
 7                  //比如，數據83  ，dp[1][0] 表示的是  80，而數據 dp[1][1]表示的是 90  
 8 int main(){      
 9     char ptr[100005];
10     scanf("%s",ptr+1);
11     /*數據的初始化，
12      * 當推到數據的第 0 位時候，表示的時候，dp[0][0] 表示的是 數字 0 ，而此時，我們只需要 0 張紙幣就可以將他們表示出來
13      * dp[0][1]表示的是數據的第0位數據，根據前面的定義，它表示的數據  1 ，由題，我們需要 1 張 1 元的紙幣就可以將它表示清楚  
14     */
15     dp[0][0]=0;
16     dp[0][1]=1;
17     int len=strlen(ptr+1);
18     /*每一位數據表示的錢數都有兩種付錢的方式：
19     比說，我這有 8 元，第一種方式是直接給8張一元的紙幣付清
20                        第二種方式是獻給一張10元的再找2張1元的，總共涉及到 3 張紙幣，
21                        這是兩種給錢的方式而下麵就是遍歷每一位數字，求出每一位數字給清的最下錢的張數
22                        之後求和即可
23     */
24     for(int i=1;i<=len;i++){//開始對數據進行迴圈遍歷
25         dp[i][0]=min(dp[i-1][0]+(ptr[i]-'0')/*表示的是直接給*/,dp[i-1][1]+10-(ptr[i]-'0')/*比如說，我這有 */);
26         dp[i][1]=min(dp[i-1][0]+(ptr[i]-'0')+1,dp[i-1][1]+10-(ptr[i]-'0')-1);
27         /*這裡為什麼要求當前位子所表示的數據+1所付清的錢的張數呢？我是這樣想的，他這裡是一個遞歸的過程，當i==1時，你在這裡求出加一時的最小張數，當i==2時，這裡就變成了多增加10的最小張數10了
28          *通過這樣一層層算出來，dp[i][0] 永遠存儲的是表示當前錢數所需的最少張數。
29         */
30     }
31     cout<<dp[len][0]<<endl;
32     return 0;
33 }