题意:对于一个序列,令一个 \(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