2020年3月21日Benelux Algorithm Programming Contest 2019

0
9

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 }

<

发布回复

请输入评论!
请输入你的名字