题解：AT_abc442_f [ABC442F] Diagonal Separation 2

Star_F · 2026-01-25 08:24:41 · 题解

我们假设第 i 行的前 k_i 个为白色。那么由于列的限制，(i-1,k_i) 这个点也必须为白色，也就是说 k_{i-1}\ge k_i，只有这样才能保证 (i-1,k_i) 为白色。

所以问题转换为，求出一个序列满足 k_1 \ge k_2 \ge \cdots \ge k_n。于是我们设 f_{i,j} 表示已经确定完前 i 个数，且第 i 个数为 j 的最小花费。转移如下：

其中 W_{i,j} 表示 将第 i 行的前 j 个格子涂白、其余格子涂黑时，单次所需的操作次数。

时间复杂度 \mathcal{O}(n^3)，考虑优化。我们发现转移的形式是一个后缀最小值于是我们直接维护一个后缀最小值的数组 \mathcal{O}(1) 转移，W_{i,j} 的计算可以由 W_{i,j-1} 简单计算，时间复杂度 \mathcal{O}(n^2)。

代码里使用滚动数组压缩掉了第一维，并且直接复用 f 为后缀最小值数组，很精简。

代码：

namespace Star_F{
    const int N = 5005;
    int n, dp[N];
    string S;
    void Main(){
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> S;
            if (i > 0)
                for (int j = n - 1; j >= 0; j--)
                    dp[j] = min(dp[j], dp[j + 1]);
            int cnt = 0;
            for (char c : S) cnt += (c == '.');
            int c1 = 0, c2 = 0;
            for (int j = 0; j <= n; j++){
                dp[j] += c1 + cnt - c2;
                if (j < n){
                    if (S[j] == '#') c1++;
                    else c2++;
                }
            }
        }
        for (int i = 1; i <= n; i++) dp[0] = min(dp[0], dp[i]);
        cout << dp[0] << endl;
    }
}