难度1
这题看到一点思路也没有,但是看到最小操作数想到二分,dp和贪心,二分答案的check显然不会,贪心不会。发现对于一行,前面的\(i-2\)是不会影响的,这一行也不会影响后面的\(i+2\)行,所以是dp。考虑如何设计状态因为\(i-1\)和\(i+1\)行都会影响,所以设计出来一个dp[i][0/1][0/1][0/1]的东西,转移方程很好推,如
注意分讨和边界情况,尤其是CF题
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],dp[1005][2][2][2];
int go(int x,int y){
if(x==0) return y;
else return 1-y;
}
bool check(int x,int i1,int y,int i2,int z,int i3){
for(int i=1;i<=m;i++){
if(go(i2,a[y][i])!=go(i1,a[x][i])&&go(i2,a[y][i])!=go(i3,a[z][i])&&a[y][i]!=a[y][i-1]&&a[y][i]!=a[y][i+1]){
return false;
}
}
return true;
}
bool check1(int x,int i1,int y,int i2){
for(int i=1;i<=m;i++){
if(go(i1,a[x][i])!=go(i2,a[y][i])&&a[x][i]!=a[x][i-1]&&a[x][i]!=a[x][i+1]){
return false;
}
}
return true;
}
bool check2(int x,int i1,int y,int i2){
for(int i=1;i<=m;i++){
if(go(i1,a[x][i])!=go(i2,a[y][i])&&a[y][i]!=a[y][i-1]&&a[y][i]!=a[y][i+1]){
return false;
}
}
return true;
}
int main(){
memset(dp,0x3f,sizeof(dp));
memset(a,-1,sizeof(a));
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
if(n==1&&m==1) cout<<-1<<endl;
else if(n==1){
for(int i=2;i<=m;i++){
if(a[1][i]!=a[1][i-1]){
cout<<"-1"<<endl;
return 0;
}
}
cout<<0<<endl;
}else if(n==2){
if(check1(1,0,2,0)&&check2(1,0,2,0)) cout<<0<<endl;
else if(check1(1,0,2,1)&&check2(1,0,2,1)) cout<<1<<endl;
else if(check1(1,1,2,0)&&check2(1,1,2,0)) cout<<1<<endl;
else if(check1(1,1,2,1)&&check2(1,1,2,1)) cout<<2<<endl;
else cout<<-1<<endl;
}else{
if(check1(1,0,2,0)) dp[1][0][0][0]=0;
if(check1(1,0,2,1)) dp[1][0][0][1]=0;
if(check1(1,1,2,0)) dp[1][0][1][0]=1;
if(check1(1,1,2,1)) dp[1][0][1][1]=1;
for(int i=2;i<=n-1;i++){
if(check(i-1,0,i,0,i+1,0)) dp[i][0][0][0]=min(dp[i-1][1][0][0],dp[i-1][0][0][0]);
if(check(i-1,0,i,0,i+1,1)) dp[i][0][0][1]=min(dp[i-1][1][0][0],dp[i-1][0][0][0]);
if(check(i-1,0,i,1,i+1,0)) dp[i][0][1][0]=min(dp[i-1][1][0][1],dp[i-1][0][0][1])+1;
if(check(i-1,0,i,1,i+1,1)) dp[i][0][1][1]=min(dp[i-1][1][0][1],dp[i-1][0][0][1])+1;
if(check(i-1,1,i,0,i+1,0)) dp[i][1][0][0]=min(dp[i-1][1][1][0],dp[i-1][0][1][0]);
if(check(i-1,1,i,0,i+1,1)) dp[i][1][0][1]=min(dp[i-1][1][1][0],dp[i-1][0][1][0]);
if(check(i-1,1,i,1,i+1,0)) dp[i][1][1][0]=min(dp[i-1][1][1][1],dp[i-1][0][1][1])+1;
if(check(i-1,1,i,1,i+1,1)) dp[i][1][1][1]=min(dp[i-1][1][1][1],dp[i-1][0][1][1])+1;
}
if(check2(n-1,0,n,0)) dp[n][0][0][0]=min(dp[n-1][1][0][0],dp[n-1][0][0][0]);
if(check2(n-1,0,n,1)) dp[n][0][1][0]=min(dp[n-1][1][0][1],dp[n-1][0][0][1])+1;
if(check2(n-1,1,n,0)) dp[n][1][0][0]=min(dp[n-1][1][1][0],dp[n-1][0][1][0]);
if(check2(n-1,1,n,1)) dp[n][1][1][0]=min(dp[n-1][1][1][1],dp[n-1][0][1][1])+1;
if(min(min(dp[n][0][0][0],dp[n][0][1][0]),min(dp[n][1][0][0],dp[n][1][1][0]))>100000) cout<<-1<<endl;
else cout<<min(min(dp[n][0][0][0],dp[n][0][1][0]),min(dp[n][1][0][0],dp[n][1][1][0]))<<endl;
}
return 0;
}
标签:return,思想,int,ABC283E,1005,check,dp
From: https://www.cnblogs.com/wuhupai/p/18036290