AtCoder Beginner Contest 283 E - Don‘t Isolate Elements

素颜马尾好姑娘i 2024-03-30 01:29 61阅读 0赞

[E - Don't Isolate Elements (atcoder.jp)][E - Don_t Isolate Elements _atcoder.jp]

题意：

![96061858e1021e5dda832e96a6cd74e1.png][]

题意：

定义孤独的数为，该数上下左右的数都和它相反

给定一个01矩阵，每次操作可以把某一行的数取反，问你把该矩阵变成没有孤独的数的最少操作次数是多少

思路：

一开始想用贪心，但是贪心想不清楚，于是去考虑dp

它是一行一行操作的，因此它是按行去划分阶段

对于某一行，我们有没有必要去取反，取决于上一层的状态

即第i-1层的状态影响了第i层的决策

因此我们定义状态为：dp\[i\]\[j\]，表示考虑操作前i行，使前i行没有孤独的数的最少操作次数，其中第i-1行的取反状态为j

然后考虑转移方程，第i层如果能和第i-1层合法，即和上一层搭配不会有孤独的数出现，就考虑转移

对于DP问题的枚举顺序，一般是先去枚举阶段，然后枚举状态，最后去枚举决策

所以我们先去枚举行，然后枚举该层的取反状态，最后枚举上一层的取反状态

其中0表示没有取反，1表示已经取反，然后把a\[i\]异或上状态，就是操作之后的数了

用异或取反这个trick好像挺方便的，表示是否取反

这个其实很像状压DP的感觉，只不过这里每一行的状态很少

for(int i=1;i<=n;i++){
            for(int j=0;j<=1;j++){
                for(int k=0;k<=1;k++){
                    for(int v=0;v<=1;v++){
                        if(check(i,j,k,v)){
                            dp[i][j][k]=min(dp[i][j][k],dp[i-1][k][v]+j);
                        }
                    }
                }
            }
        }

然后另一个难点是怎么去check

其实思路很简单，就是容易写错QwQ

check函数里面就是去枚举列，对于该列如果和上下两行有孤独的数出现，不合法，否则就合法

注意第一行和最后一行的特判，这两行没有上一行和下一行

最后去枚举状态，统计最小值即可，如果是无穷就是-1

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e3+10;
    int n,m;
    int a[mxn][mxn],dp[mxn][2][2];
    bool check(int c,int x,int y,int z){
        c--;
        if(c==0){
            return true;
        }else if(c==1){
            for(int i=1;i<=m;i++){
                int ok=0;
                if((a[c][i]^y)==(a[c+1][i]^x)) ok=1;
                if(i+1<=m&&a[c][i]==a[c][i+1]) ok=1;
                if(i-1>=1&&a[c][i]==a[c][i-1]) ok=1;
                if(!ok) return false;
            }
            return true;
        }else if(c!=n-1){
            for(int i=1;i<=m;i++){
                int ok=0;
                if(((a[c][i]^y)==(a[c+1][i]^x))||(a[c][i]^y==a[c-1][i]^z)) ok=1;
                if(i+1<=m&&a[c][i]==a[c][i+1]) ok=1;
                if(i-1>=1&&a[c][i]==a[c][i-1]) ok=1;
                if(!ok) return false;
            }
            return true;
        }else{
            c++;
            for(int i=1;i<=m;i++){
                int ok=0;
                if((a[c][i]^x)==(a[c-1][i]^y)) ok=1;
                if(i+1<=m+1&&a[c][i]==a[c][i+1]) ok=1;
                if(i-1>=1&&a[c][i]==a[c][i-1]) ok=1;
                if(!ok) return false;
            }
            return true;
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cin>>a[i][j];
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0][0][0]=dp[0][0][1]=dp[0][1][0]=dp[0][1][1]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=1;j++){
                for(int k=0;k<=1;k++){
                    for(int v=0;v<=1;v++){
                        if(check(i,j,k,v)){
                            dp[i][j][k]=min(dp[i][j][k],dp[i-1][k][v]+j);
                        }
                    }
                }
            }
        }
        int ans=1e18;
        for(int j=0;j<=1;j++){
            for(int k=0;k<=1;k++) ans=min(ans,dp[n][j][k]);
        }
        if(ans==1e18) ans=-1;
        cout<<ans<<'\n';
    }

[E - Don_t Isolate Elements _atcoder.jp]: https://atcoder.jp/contests/abc283/tasks/abc283_e
[96061858e1021e5dda832e96a6cd74e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7943595c0ab64c57b599e14357896a86.png