[题解] CF1990D Grid Puzzle

Monke_FClBrI · 2024-07-21 13:44:48 · 题解

Links: [Codeforces] [Luogu]

题意

给定一个长为 n 的非负整数序列 a。有一个 n\times n 的方格图，其中第 i 行中的靠左的 a_i 个格子为黑色，其余格子为白色。你可以进行若干次以下操作之一：

• 选择图中一个 2\times 2 的子矩形染成白色；
• 选择图中一行格子染成白色。

问让每个格子都变为白色至少需要多少次操作。每个测试点 t 组测试用例。

思路

看到这题首先有个很简单的想法：如果有连续的两行黑格数都小于等于 2，那么就染方块，否则就染一整行，因为在同一组相邻的行放两个方块显然不优于直接分别染两行。然后发现样例第二组爆炸了，因为它可以用三个方块叠成两层，比上面这个更优。

然后我们思考会不会有方块叠成更多层，可以发现如果我们要在某个行上覆盖三个方块，那么显然这样只能覆盖至多 2 行的黑格，所以显然是劣于直接染两行的。同理，叠更多层显然就更劣了。因此我们最多只会用方块叠两层，并且是这样交替地叠。

然后考虑用 DP 求解。设 f_{i,0/1/2} 表示填完了前 i 行，第 i 行 没有填方块 / 填了一个 1,2 两列的方块 / 填了一个 3,4 两列的方块 的最小操作次数（这里“在第 i 行填方块”指的是在第 i 和 i+1 行和指定列填方块，下同）。考虑转移：

• 第 i 行不填，那么要么是 a_i=0，要么是 a_i\le 2 且前一行填了 1,2 列。
• 第 i 行填整行，那么要求前一行没有填方块（因为前一行填方块，本行填整行的方案总是不优于两行都填整行）。
• 第 i 行 1,2 列填方块，如果 a_i\le 2，那么可以 i-1 行不填方块；如果 a_i\le 4 那么可以 i-1 行填 3,4 列，第 i 行插进去。
• 第 i 行 3,4 列填方块，如果 a_i\le 4，那么 i-1 行填 1,2 列，第 i 行叠上去。

即转移如下：

转移到 f_{n-1}，最后处理一下即可。复杂度 O(n)。

代码

#include<bits/stdc++.h>
#define pb push_back
#define SZ(x) (int)((x).size())
using namespace std;
const int N=2e5+5,INF=1e9;
int _,n,a[N],f[N][3],ans;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>_;
    while(_--){
        cin>>n;for(int i=1;i<=n;i++)cin>>a[i],f[i][0]=f[i][1]=f[i][2]=INF;
        if(n==1){cout<<!!a[1]<<'\n';continue;}
        f[1][0]=!!a[1];if(a[1]<=2)f[1][1]=1;
        for(int i=2;i<n;i++){
            f[i][0]=f[i-1][0]+!!a[i];
            if(a[i]<=2)f[i][0]=min(f[i][0],f[i-1][1]),f[i][1]=f[i-1][0]+1;
            if(a[i]<=4)f[i][1]=min(f[i][1],f[i-1][2]+1),f[i][2]=f[i-1][1]+1;
        }
        ans=f[n-1][0]+!!a[n];if(a[n]<=2)ans=min(ans,f[n-1][1]);
        cout<<ans<<'\n';
    }
    return 0;
}

（逃