专栏文章

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

cchenyunting
P12211题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipe905p
此快照首次捕获于
2025/12/03 10:34
3 个月前
此快照最后确认于
2025/12/03 10:34
3 个月前
查看原文

思路

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

定义状态

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

决策

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

  • 如果前一个单词‌不翻转‌：
    检查当前单词的首字符与前一单词的末尾字符是否相同（a[i][0] == a[i-1][1]）。
    • 相同 → 长度叠加 +1。
    • 不同 → 长度叠加 +2。
    CPP
    bufanzhuan[i] = min(bufanzhuan[i], bufanzhuan[i-1] + (条件满足 ? 1 : 2))
  • 如果前一个单词‌翻转‌：
    检查当前单词的首字符与前一翻转单词的首字符是否相同（a[i][0] == a[i-1][0]）。
    • 相同 → 长度叠加 +1。
    • 不同 → 长度叠加 +2。
    CPP
    bufanzhuan[i] = min(bufanzhuan[i], fanzhuan[i-1] + (条件满足 ? 1 : 2))

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

  • 如果前一个单词‌不翻转‌：
    检查当前单词的末尾字符（翻转后的首字符）与前一单词的末尾字符是否相同（a[i][1] == a[i-1][1]）。
    • 相同 → 长度叠加 +1。
    • 不同 → 长度叠加 +2。
    CPP
    fanzhuan[i] = min(fanzhuan[i], bufanzhuan[i-1] + (条件满足 ? 1 : 2))
  • 如果前一个单词‌翻转‌：
    检查当前单词的末尾字符（翻转后的首字符）与前一翻转单词的首字符是否相同（a[i][1] == a[i-1][0]）。
    • 相同 → 长度叠加 +1。
    • 不同 → 长度叠加 +2 。
    CPP
    fanzhuan[i] = min(fanzhuan[i], fanzhuan[i-1] + (条件满足 ? 1 : 2))

代码

C

#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...