第14届蓝桥杯--保险箱

第14届蓝桥杯--保险箱

DP

从后往前循环统计

1. 状态表示f[i][j]: 第i位密码数j状态, (j = 0产生退位, 1不进不退, 2产生进位)

集合: 所有的方案

属性: min

2. 状态计算:

   

import java.util.Arrays;
import java.util.Scanner;

/**
 * ClassName:Main04
 * Package:baidu
 * Description:
 *
 * @author:LH寒酥
 * @create:2023/10/27-18:28
 * @version:v1.0
 */
public class Main {
    static final int N = 100002, INF = 0x3f3f3f3f;
    static int[][] f = new int[N][3];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < 3; j ++ )
                f[i][j] = INF;

        if (s1.charAt(n - 1) - s2.charAt(n - 1) >= 0) {
            f[n - 1][1] = s1.charAt(n - 1) - s2.charAt(n - 1);
            f[n - 1][2] = s2.charAt(n - 1) + 10 - s1.charAt(n - 1);
        } else {
            f[n - 1][1] = s2.charAt(n - 1) - s1.charAt(n - 1);
            f[n - 1][0] = s1.charAt(n - 1) + 10 - s2.charAt(n - 1);
        }

        for (int i = n - 2; i >= 0; i -- ) {
            if (s1.charAt(i) > s2.charAt(i)) {
                int t = s1.charAt(i) - s2.charAt(i);
                f[i][1] = Math.min(Math.min((f[i + 1][0] + t - 1), f[i + 1][1] + t), f[i + 1][2] + t + 1);
                t = s2.charAt(i) + 10 - s1.charAt(i);
                f[i][2] = Math.min(Math.min((f[i + 1][0] + t + 1), f[i + 1][1] + t), f[i + 1][2] + t - 1);
            } else if (s1.charAt(i) == s2.charAt(i)) {
                f[i][1] = Math.min(Math.min((f[i + 1][0] + 1), f[i + 1][1]), f[i + 1][2] + 1);
            } else {
                int t = s2.charAt(i) - s1.charAt(i);
                f[i][1] = Math.min(Math.min((f[i + 1][0] + t + 1), f[i + 1][1] + t), f[i + 1][2] + t - 1);
                t = s1.charAt(i) + 10 - s2.charAt(i);
                f[i][0] = Math.min(Math.min((f[i + 1][0] + t - 1), f[i + 1][1] + t), f[i + 1][2] + t + 1);
            }
        }

        System.out.println(Math.min(Math.min(f[0][0], f[0][1]), f[0][2]));
    }
}