题解

Difficulty：3.1 / Easy

Tag：-

定义 $\text{dp}_{i,j}$ 表示前 $i$ 张牌，第 $i$ 张牌翻面或不翻面的最小值。没了。

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		std::vector <int> a(n + 5), b(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		for(int i = 1; i <= n; i++){
			std::cin >> b[i];
		}
		std::vector <std::vector <ll>> dp(n + 5, std::vector <ll>(2, 0x3f3f3f3f3f3f3f3fll));
		dp[1][0] = dp[1][1] = 0;
		for(int i = 2; i <= n; i++){
			dp[i][0] = std::min(dp[i - 1][0] + abs(a[i - 1] - a[i]), dp[i - 1][1] + abs(b[i - 1] - a[i]));
			dp[i][1] = std::min(dp[i - 1][0] + abs(a[i - 1] - b[i]), dp[i - 1][1] + abs(b[i - 1] - b[i]));
		}
        std::cout << std::min(dp[n][0], dp[n][1]) << '\n';
	}
}

时间复杂度：$O(n)$。