首页 > 其他分享 >CF818G - Four Melody

CF818G - Four Melody

时间:2023-02-23 21:24:43浏览次数:39  
标签:Juc cnt 后缀 ik Four add CF818G Melody id

题意:对于一个序列,令一个 \(melody\) 为一个子序列满足子序列的相邻两项相差 \(1\) 或者模 \(7\) 同余。现在提取四个不重合的 \(melody\),求最长总长度。

我们先考虑暴力的网络流,每个点拆成两个,中间流量 \(1\),费用 \(-1\),每个点朝着所有可以转移向的点连边。边数是 \(O(n^2)\) 的。总复杂度 \(O(n^3)\)。

我们发现,我们不一定要往所有可以转移的点连边。我们可以建立两种点,一种是“值点”,一种是“模点”。我们只是往所有的“值为 \(a_i\pm 1\) 的后缀”和所有“模 \(7\) 为 \(k\) 的后缀”连边。这些后缀连到自己所属的值。然后后缀再连到新的后缀。

但是,如果我们给每个位置都开这样的后缀,点数就会变成 \(O(n^2)\)(离散化后),反而不如原来。不过我们发现,如果位置 \(i\) 没有值为 \(x\) 的数或模 \(7\) 余 \(k\) 的数,后缀 \(x\) 和 \(k\) 就可以和 \(i+1\) 共用。

这就提示我们遇到了再对当前值的后缀更新新节点并连边。

我们记录当前值为 \(x\) 的后缀是 \(id_x\),当前模 \(7\) 余 \(x\) 的后缀是 \(ik_x\)。

首先,\(x\) 从 \(id_{a_x}\) 转移来,更新新的 \(id_{a_x}\)

然后,\(x\) 转移到 \(id_{a_x\pm1}\),更新新的 \(id_{a_x\pm1}\)

最后,\(x\) 从 \(ik_{a_x\bmod 7}\) 转移来,更新,转移到新的 \(ik_{a_x\bmod 7}\)。

因为最多提出四个子序列,我们建立虚拟源点,让一切流量从这里流出,而源点到虚拟源点连流量为 \(4\) 的边。

边数 \(O(n)\),总复杂度 \(O(n^2)\),足够通过此题。

int id[100005],ik[8],n,a[3005],cnt;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rp(i,n)cin>>a[i];cnt=2*n+1;
	Juc::s=0,Juc::t=2*n+2,cnt=2*n+2;
	rep(i,0,2*n+2)Juc::ptt(i);
	Juc::add(0,2*n+1,4,0);
	rp(i,n){
		Juc::add(2*n+1,i,1,0);
		Juc::add(i+n,2*n+2,1,0);
		Juc::add(i,i+n,1,-1);
		
		if(id[a[i]-1]){
			++cnt;Juc::ptt(cnt);
			Juc::add(id[a[i]-1],i,1,0);
			Juc::add(id[a[i]-1],cnt,1e9,0);
			id[a[i]-1]=cnt;
		}
		
		if(id[a[i]+1]){
			++cnt;Juc::ptt(cnt);
			Juc::add(id[a[i]+1],i,1,0);
			Juc::add(id[a[i]+1],cnt,1e9,0);
			id[a[i]+1]=cnt;
		}
		
		++cnt;Juc::ptt(cnt);
		if(id[a[i]]){
			Juc::add(id[a[i]],cnt,1e9,0);
			Juc::add(id[a[i]],i,1e9,0);
		}id[a[i]]=cnt;
		Juc::add(i+n,id[a[i]],1,0);
		
		++cnt;Juc::ptt(cnt);
		if(ik[a[i]%7]){
			Juc::add(ik[a[i]%7],i,1,0);
			Juc::add(ik[a[i]%7],cnt,1e9,0);
		}
		Juc::add(i+n,cnt,1,0);ik[a[i]%7]=cnt;
	}
	Juc::MCMF();
	cout<<-Juc::cost<<endl;
	return 0;
}
//Crayan_r

标签:Juc,cnt,后缀,ik,Four,add,CF818G,Melody,id
From: https://www.cnblogs.com/jucason-xu/p/17149444.html

相关文章

  • HODJ1197 Specialized Four-Digit Numbers
    SpecializedFour-DigitNumbersTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):7715    Accepted......
  • LESSON FOUR:Java基础语法(上)
    Java基础语法注释单行注释://注释内容多行注释:/*注释内容*/文档注释:/**注释内容*//*.---..-----------*/\__/------*......
  • the fourteenth——20223.1.6
    #include<stdio.h>intmain(){ 3,4,5;//这是一条语句 //把上面这条语句的值赋值给变量a inta=(3,4,5); printf("a=%d\n",a);}输出结果:a=5因为a的值是整......
  • the fourth—2022.12.25
    整数(int):计算机以二进制储存整数 在8字节中00000111=716位的int的取值范围-32768~32767,当大于取值范围时,会从取值范围的第一个重新开始取值。即输入32768,则会输出-32768......
  • HCIE-桌面云运营Four
    桌面云快速发放流程登录FC平台制作虚拟机模板模板制作流程创建空的虚拟机挂载光驱,按照操作系统关闭防火墙切换超级管理员账号挂载模板制作工具链接克隆无手动......
  • HCIE-服务器虚拟化运营Four
    FusionCompute平台网络平面及规划类型管理平面存储平面业务平面BMC平面规划原则管理要主备部署(两张网卡)存储流量占比高(两张网卡)管理和业务可绑定在一起......
  • weekfour——周总结
    weekfour——周总结正则表达式前戏'''案例:京东注册手机号校验基本需求:手机号必须是11位、手机号必须以1315开头、必须是纯数字'''phone=input('请输入您的手......
  • CF818G Four Melodies 压缩图建边
    看到题解有压缩图的tag,以为是很高大上的玩意点进去发现竟然是不要建多余的边捏..正确性:如果a->下一个和它值差为1的元素,那么后面还有好几个和它值差为1的元素呢?能完美......
  • 2022 ICPC 网络赛(II) H Fast Fourier Transform题解
    简要题意给你一棵树,你可以选若干节点为关键点,定义一个选点方案的价值为:所有路径上没有关键点的点对的距离之和。求所有选点方案的价值之和。题解一开始和队友都读错题了......
  • Four Points
    ProblemStatementThereisarectangleinthe$xy$-plane.Eachedgeofthisrectangleisparalleltothe$x$-or$y$-axis,anditsareaisnotzero.Giventhe......