首页 > 其他分享 >ABC283E (dp思想)

ABC283E (dp思想)

时间:2024-02-27 10:11:19浏览次数:25  
标签:return 思想 int ABC283E 1005 check dp

难度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

相关文章

  • P10156(dp思想)
    难度2也是比较有意思的一道题。首先发现每个小团体独立,所以对于每个小团体分开直接暴力dp,dp[i][j]表示当前小团体做到第i人,走了j人,然后O(n)转移,加上部分分喜提50pts。为什么要O(n)转移呢,因为我要枚举匹配的两个人然后算贡献。但是对于这种带绝对值的贡献,我们一般都要把绝对值拆掉......
  • CF1928C (数学思想)
    难度3其实是有点虚高的,可能是我这种数学题做的少了。在考试时式子都写出来了,但不知道怎么处理。然后注意一下细节就可以了。懒懒懒。对于xy=k(k为常数)可以直接枚举k的因子,然后看一下限制条件即可。#include<bits/stdc++.h>usingnamespacestd;longlongT,n,x,tot=0;unorde......
  • P6805 (树上最小路径覆盖思想)
    难度3比较有意思的一道题。首先看到题目是求树上最小路径覆盖,自然想到由叶子入手去分析,所以当子树内有偶数个叶子节点时,那么就有两个叶子向上匹配,否则只有一个叶子向上匹配。这个东西可以用树剖维护,线段树维护的是子树内有多少个偶的,相当于一个区间反转一类的东西。细节不算多,但......
  • P1240+P1350+ AT_abc282_g得出的一些dp技巧
    在遇到一些题目在设状态时,前面的状态对后面的有影响,比如在P1240和P1350中前面的放置会对后面的有影响,正常的状态是不行的。以前可能考虑状态压缩,但现在我们可以通过发现前面状态的一些共性,比如在P1240+P1350中前面放了k个車那么一定有k行被占用,所以就不用记录之前那些行被占用了。......
  • P4666 [BalticOI 2011 Day1] Growing Trees题解(平衡树思想)
    自己第一道不看题解写出来的紫题,庆祝一下(没初始化种子导致调了30min)这是一个fhq-treap的题解思路来源:首先看题目,因为是序列上的问题,不难想到是一道数据结构题。首先看到操作C:对于这种操作,我们可以用平衡树解决,具体方法是,将树split成\(<min,min\lex\lemax,>max\)这......
  • 【学习笔记】树型DP学习笔记
    学习笔记索引省流:被吊打了自己开的一个坑,死也要填完它。希望我随手写下的笔记对您的学习有所帮助(也不太可能)。更改日志2024/01/08:开坑,写了树的直径和换根DP,写不动了(((2024/01/08晚上:更新了最小点覆盖和最大独立集,看来精神还可以,顶着明天做手术的风险2024/01/09:修改错误+增补......
  • Exception in thread "xxl-job, admin JobRegistryMonitorHelper-registryOrRemoveThr
    这个问题集合遍历修改了集合结构,这样是不被允许的,需要换种方式报错示意图 第一可以采用for(inti=0;i<registryList.size();i++)解决第二采用迭代处理Iterator<XxlJobRegistry>iterator=registryList.iterator();while(iterator.hasNext()){XxlJobRegist......
  • 519-基于ZU19EG的4路100G 网络 DPU的PCIe 加速计算卡 高速信号处理卡 ZU19EG处理板 高
    基于ZU19EG的4路100G网络DPU的PCIe加速计算卡  一、板卡概述   本板卡系北京太速科技自主设计研发,基于Xilinx公司ZynqUltraScale+MPSOC系列SOCXCZU19EG-FFVC1760架构,支持PCIEGen3x16模式。其中,ARM端搭载一组64-bitDDR4,总容量达4GB,可稳定运行在2400MT/s,PL端支......
  • 漂亮网格(DP)
    第2题   漂亮网格 查看测评数据信息n行m列的二维网格,每个格子要么是'.',要么是'#',其中'.'表示白色格子,'#'表示黑色格子。从上往下,行的编号是1至n。从左往右,列的编号是从1至m。网格被称为"漂亮网格",当且仅当同时满足如下的两个条件:1、对于任意的1<=i<=n, 1<=j<=m,如果......
  • Rockchip RK3399 - DRM edp驱动程序
    ----------------------------------------------------------------------------------------------------------------------------开发板:NanoPC-T4开发板eMMC:16GBLPDDR3:4GB显示屏:15.6英寸HDMI接口显示屏u-boot:2023.04linux:6.3----------------------------------......