< 返回新闻公共列表
云南大王-2020年3月21日Benelux Algorithm Programming Contest 2019
发布时间：2020-03-25 00:00:00
E. Efficient Exchange
题意：这一题的题意简单；简单来说就是A、B有1元10元、100元、1000元。。。。等等10的整次幂的票额的纸币，现在B付钱给A，问当中涉及钱的张数最少是多少可以把钱付清。
题解：这一题官方题解给的是DP+递归，自己看了半天，代码中的注释给出了自己的理解，
1 #include
2 #include
3 #include
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<
/template/Home/Zkeys/PC/Static
