题解：P12211 [蓝桥杯 2023 国 Python B] 翻转

chenyunting · 2025-05-06 17:33:53 · 题解

思路

这是一道动态规划的题目，每个工件有翻转和不翻转两种情况。

定义状态

• fanzhuan[i] 表示前 i 个单词中第 i 个单词要翻转的最优解。
• bufanzhu 表示前 i 个单词中第 i 个单词不翻转的最优解。

决策

‌更新 bufanzhuan[i]（第 i 个不翻转）‌

• 如果前一个单词‌不翻转‌：
  检查当前单词的首字符与前一单词的末尾字符是否相同（a[i][0] == a[i-1][1]）。
  • 相同 → 长度叠加 +1。
  • 不同 → 长度叠加 +2。

    bufanzhuan[i] = min(bufanzhuan[i], bufanzhuan[i-1] + (条件满足 ? 1 : 2))

• 如果前一个单词‌翻转‌：
  检查当前单词的首字符与前一翻转单词的首字符是否相同（a[i][0] == a[i-1][0]）。
  • 相同 → 长度叠加 +1。
  • 不同 → 长度叠加 +2。

    bufanzhuan[i] = min(bufanzhuan[i], fanzhuan[i-1] + (条件满足 ? 1 : 2))

‌更新 fanzhuan[i]（第 i 个翻转）‌

• 如果前一个单词‌不翻转‌：
  检查当前单词的末尾字符（翻转后的首字符）与前一单词的末尾字符是否相同（a[i][1] == a[i-1][1]）。
  • 相同 → 长度叠加 +1。
  • 不同 → 长度叠加 +2。

    fanzhuan[i] = min(fanzhuan[i], bufanzhuan[i-1] + (条件满足 ? 1 : 2))

• 如果前一个单词‌翻转‌：
  检查当前单词的末尾字符（翻转后的首字符）与前一翻转单词的首字符是否相同（a[i][1] == a[i-1][0]）。
  • 相同 → 长度叠加 +1。
  • 不同 → 长度叠加 +2 。

    
    fanzhuan[i] = min(fanzhuan[i], fanzhuan[i-1] + (条件满足 ? 1 : 2))

代码

#include <iostream>
#include <algorithm>
#include <climits>
namespace noip {
typedef long long ll;
constexpr ll MAX_N_c = 100000;
ll n;
char a[1+MAX_N_c][2];
ll fanzhuan[1+MAX_N_c], bufanzhuan[1+MAX_N_c];
void main() {
    std::cin >> n;
    for (ll i = 1; i <= n; i++)
        std::cin >> a[i];

    fanzhuan[1] = bufanzhuan[1] = 2;
    for (ll i = 2; i <= n; i++) {
        bufanzhuan[i] = fanzhuan[i] = LLONG_MAX;
        if (a[i][0] == a[i-1][1])
            bufanzhuan[i] = std::min(bufanzhuan[i], bufanzhuan[i-1]+1);
        else
            bufanzhuan[i] = std::min(bufanzhuan[i], bufanzhuan[i-1]+2);
        if (a[i][0] == a[i-1][0])
            bufanzhuan[i] = std::min(bufanzhuan[i], fanzhuan[i-1]+1);
        else
            bufanzhuan[i] = std::min(bufanzhuan[i], fanzhuan[i-1]+2);
        if (a[i][1] == a[i-1][1])
            fanzhuan[i] = std::min(fanzhuan[i], bufanzhuan[i-1]+1);
        else
            fanzhuan[i] = std::min(fanzhuan[i], bufanzhuan[i-1]+2);
        if (a[i][1] == a[i-1][0])
            fanzhuan[i] = std::min(fanzhuan[i], fanzhuan[i-1]+1);
        else
            fanzhuan[i] = std::min(fanzhuan[i], fanzhuan[i-1]+2);
    }

    std::cout << std::min(fanzhuan[n], bufanzhuan[n]);
}
}

int main() {
    noip::main();
    return 0;
}