第14届蓝桥杯--保险箱
DP
从后往前循环统计
- 状态表示f[i][j]: 第i位密码数j状态, (j = 0产生退位, 1不进不退, 2产生进位)
集合: 所有的方案
属性: min
-
状态计算:
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]));
}
}