CF818G - Four Melody
题意:对于一个序列,令一个 \(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
最新文章
- TCPIP、Http、Socket的协议~ 写得挺形象,赞
- Activity详解三 启动activity并返回结果
- PHP的PDO
- 创建menu文件
- 创建eclipse针对NDK的联合编译环境。
- (转)MyEclipse自动生成Hibernate实体类, oracle篇
- CSS3图片旋转特效
- OC基础 代理和协议
- satellite-menu和ArcMenu
- 七天学会NodeJS
- 2-13. 平均两个有序序列(25)(ZJU_PAT 名单 | 排列 )
- CentOS 7中将Tomcat设置为系统服务
- 在Express中安装XTemplate
- 福利:1H1G2M云服务器限时15元/月,买2送1,一年加6个月只要180元
- 【记录】垃圾清理软件 便携版CleanMyPC破解版
- WINDOWS 下设置单独的java环境
- js把预定义的html字符串转换为 HTML 实体 htmlspecialchars 输出html实体内容包括标签,而不自动转义标签,只显示内容,类似php的htmlspecialchars
- linux下给php安装curl、gd(ubuntu)
- DAY2-Python学习笔记
- [JZOJ6088] [BZOJ5376] [loj #2463]【2018集训队互测Day 1】完美的旅行【线性递推】【多项式】【FWT】