解题思路:
1、坐标压缩
只关注原来含 # 的列,将这些列的下标收集到数组 col[1..k],对应的行掩码(1 表示只在上行,2 表示只在下行,3 表示两行都有)收集到 mask[1..k]。
这样DP只需在 k 列之间做,时间从 O(n)降到O(k)。
2、滚动数组
因为每列的状态只依赖前一列,故用两个变量 prev0, prev1 分别表示“到上一活跃列且最后在上行/下行的最小新增数”,空间 O(1)。
3、状态转移
从第 i−1 个活跃列过渡到第 i个活跃列,需要:
横向补空格:列间空列数Δ = col[i] − col[i − 1] − 1;
跨行切换:如果上一列在行 rrr,本列想落在另一个行 r′≠r,则需在本列“竖直”再放一个探测器(由 cross[r'] 表示,0/1);
本列补探测器:如果原来本列目标行没有 #,则需再放一个(由 cost[r'] 表示,0/1)。
因此,令:
cur0 = min(prev0, prev1 + cross0) + Δ + cost0;
cur1 = min(prev1, prev0 + cross1) + Δ + cost1;
然后将 prev0=cur0, prev1=cur1,推进到下一列。
4、快速 I/O
使用 getchar_unlocked 批量读两行字符串,保证 nnn 达到 10610^6106 时也能迅速读取。
注意事项:
参考代码:
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000005
#define INF 0x3f3f3f3f
// 使用 getchar_unlocked 快速读入一行到 buf 中,返回长度
static int fast_read_line(char *buf) {
int c, len = 0;
# 用 getchar_unlocked 一次性读字符,比 scanf 更快。
while ((c = getchar_unlocked()) != EOF && c != '\n') {
buf[len++] = (char)c;
}
buf[len] = '\0';
return len;
}
// 取两数最小
static inline int min(int a, int b) {
return a < b ? a : b;
}
int main() {
static char s1[MAXN], s2[MAXN];
int n = fast_read_line(s1);
fast_read_line(s2); // 同样长度 n
// 收集所有含 '#’ 的列
static int col[MAXN], mask[MAXN];
int k = 0;
for (int i = 0; i < n; i++) {
int m = 0;
if (s1[i] == '#') m |= 1;
if (s2[i] == '#') m |= 2;
if (m) {
col[++k] = i;
mask[k] = m;
}
}
// 少于两列含检测器,直接 0
if (k <= 1) {
puts("0");
return 0;
}
// 首列初始化
// 末尾在行0/1的总代价
int add0 = (mask[1] & 1) ? 0 : 1;
int add1 = (mask[1] & 2) ? 0 : 1;
int prev0 = add0, prev1 = add1;
// 滚动 DP
for (int i = 2; i <= k; i++) {
int delta = col[i] - col[i-1] - 1;
// 本列需要在行0/1放探测器的代价
int cost0 = (mask[i] & 1) ? 0 : 1;
int cost1 = (mask[i] & 2) ? 0 : 1;
// 跨行切换时,还需补竖直一格的代价
int cross0 = (mask[i] & 2) ? 0 : 1; // 到行0,但上一列在行1时需要
int cross1 = (mask[i] & 1) ? 0 : 1; // 到行1,但上一列在行0时需要
int cur0 = min(prev0, prev1 + cross0) + delta + cost0;
int cur1 = min(prev1, prev0 + cross1) + delta + cost1;
prev0 = cur0;
prev1 = cur1;
}
int ans = min(prev0, prev1);
printf("%d\n", ans);
return 0;
}
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复