赞
踩
DP
从后往前循环统计
集合: 所有的方案
属性: 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])); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。