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 }

 

原文链接:https://www.cnblogs.com/blogxsc/p/12563608.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有