解题思路:

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;

}

点赞(1)
 

0.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论