5408-保险箱

5408 保险箱

题目

链接

思路与解答

1. 对于一个数字，是从左向右还是从右向左分析
   由于低位（右边）一旦进一或者借一，就会影响高位（左边），因此对于两个数字，从右向左依次分析。
2. 利用dp的思想
   本题实际考察了状态DP。
   对于第$i$位，我们考虑，变化这一位使之与目标位匹配，会被其右边的低位影响，使得其需要变动的次数+1或者-1；

解答

参考
技巧：
将字符串转为int型变量：
逐位与’0’进行-运算：

string str = "12303";
int a[100];
for (int i = 0; i < str.length();i++)
	a[i] = str[i] - '0';

对于每一位，我们都有三种情况：

• 这一位运算后既没有进位，也没有借位

• 这一位运算后进位了

• 这一位运算后向前借位了
  对于每种情况，其由上一位的状态转移过来，又有三种选择：
  我们以第一种状态：“这一位运算后既没有进位，也没有借位”为例子,也就是dp[i][0]

• 上一位既没有进位，也没有借位: dp[i][0] = dp[i + 1][0] + abs(y - x);

• 上一位进位了：dp[i][0] = dp[i+1][1] + abs(y - (x + 1));

• 上一位借位了：dp[i][0] = dp[i+1][2] + abs(y - (x - 1));
  然后取这三种可能的最小值，就是这个状态的最优解。

代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int n;
int x, y;
const int MAXN = 1e5 + 3;
int dp[MAXN][3];// dp[i][0]：当前位没有进位，dp[i][1]:当前位进位了，dp[i][2]:当前位借走了一位

int main(){
    scanf("%d", &n);
    string strx, stry;
    cin >> strx >> stry;
    int length = strx.length();
    // 初始化右边低位
    x = strx[length - 1] ^ '0';
    y = stry[length - 1] ^ '0';
    dp[length - 1][0] = abs(y - x);
    dp[length - 1][1] = 10 - x + y;
    dp[length - 1][2] = x - 0 + 10 - y;


    int t1, t2, t3;
    for (int i = length - 1 - 1; i>=0;i--){
        x = strx[i] - '0';
        y = stry[i] - '0';
        // dp[i][0]:
        t1 = dp[i + 1][0] + abs(y - x);
        t2 = dp[i + 1][1] + abs(y - (x + 1));
        t3 = dp[i + 1][2] + abs(y - (x - 1));
        dp[i][0] = min(t1, t2);
        dp[i][0] = min(dp[i][0], t3);

        // dp[i][1]:
        t1 = dp[i + 1][0] + 10 - x + y;
        t2 = dp[i + 1][1] + (10 - (x + 1) + y);
        t3 = dp[i + 1][2] + (10 - (x - 1) + y);
        dp[i][1] = min(t1, t2);
        dp[i][1] = min(dp[i][1],t3);

        // dp[i][2]:
        t1 = dp[i + 1][0] + x - 0 + 10 - y;
        t2 = dp[i + 1][1] + ((x + 1) - 0 + 10 - y);
        t3 = dp[i + 1][2] + ((x - 1) - 0 + 10 - y);
        dp[i][2] = min(t1, t2);
        dp[i][2] = min(dp[i][2], t3);
    }
    int t = min(dp[0][0], dp[0][1]);
    printf("%d",min(t, dp[0][2]));
    return 0;
}

结果