题解 CF818G 【Four Melodies】

· · 题解

update on 2021-1-21：

重制了全文，感谢 @George1123 帮助我发现算法的锅。（一年前的算法是有大量坑的）

现在使用的是正确算法。

同时修改为正确的 \LaTeX 格式。

翻译

给你 n 个数 a_1 \dots a_n，要你从这 n 个数中选出 4 个互不相交的非空子序列，并且要求：这些子序列中任意相邻的两个数 a_{x_i},a_{x_{i+1}}，都必须有 |a_{x_i}-a_{x_{i+1}}|=1 或 a_{x_i}\equiv a_{x_{i+1}}\pmod7。求这些子序列的长度之和的最大值。

数据范围：4\leq n\leq 3000,1\leq a_i\leq 10^5。

做法

我们考虑暴力的网络流做法：将每个位置拆点以限制只能被一条路径访问，然后在两个可以成为子序列中相邻元素的位置间连边，同时建立伪源点以限制只有四条路径，然后直接上最大费用最大流即可。

该做法点数是 2n，边数是 n^2，亲测过不去。考虑消减边数。

我们发现，若我们考虑“同余”的情形，则会发现每一个 \bmod7 的同余类内所有东西间都是两两有单向边的。于是我们新建 n 个节点表示此种类型，每个新建节点连向其后方第一个与其同余的新节点。我们发现，这样连边后，各个同余系中的元素所连成的东西互不干涉，可以被看作是形成了 7 条“高速公路”。i 位置的出点在此处“上高速公路”，然后在其后的任意位置都可以“下高速公路”。为了实现此功能，只需让位置 i 的出点连向其之后第一个同余节点的高速公路节点，并且从位置 i 的高速公路节点连向其入点即可。

我们再来看向第二个“差为一”的情形——a_i 连向所有其之后值为 a_i+1 和 a_i-1 的位置，本质上不是还是上述的高速公路问题嘛！我们对于每个不同的值，建一条高速公路，然后 a_i 在其之后第一个 a_i+1 的位置上 a_i+1 的高速公路，在其之后第一个 a_i-1 的位置上 a_i-1 的高速公路，在之后的位置随时可以下高速公路，就是这样。

于是此时就共需要 4n 个节点，边数被消减到 O(n)。可以通过。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,num[3010],s;
namespace MCMF{
    const int N=15000,M=2000000;
    int head[N],cnt,dis[N],fr[N],id[N],S,T,cost;
    struct node{
        int to,next,val,cost;
    }edge[M];
    void ae(int u,int v,int w,int c){
//      printf("%d %d (%d,%d)\n",u,v,w,c);
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    bool in[N];
    bool SPFA(){
        memset(dis,-1,sizeof(dis)),dis[S]=0,q.push(S),in[S]=true;
        while(!q.empty()){
            int x=q.front();q.pop(),in[x]=false;
    //      printf("%d\n",x);
            for(int i=head[x];i!=-1;i=edge[i].next){
                if(!edge[i].val)continue;
                if(dis[edge[i].to]<dis[x]+edge[i].cost){
                    dis[edge[i].to]=dis[x]+edge[i].cost,fr[edge[i].to]=x,id[edge[i].to]=i;
                    if(!in[edge[i].to])in[edge[i].to]=true,q.push(edge[i].to);
                }
            }
        }
        if(dis[T]==-1)return false;
        int x=T,mn=0x3f3f3f3f;
        while(x!=S)mn=min(mn,edge[id[x]].val),x=fr[x];
        cost+=dis[T]*mn,x=T;
        while(x!=S)edge[id[x]].val-=mn,edge[id[x]^1].val+=mn,x=fr[x];
        return true;
    }
}
using namespace MCMF;
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head)),S=4*n+1,T=4*n+2,s=4*n+3,ae(S,s,4,0);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]);
    for(int i=1;i<=n;i++){
//0:of the same reminder  1:of the same value  2,3: assistive nodes for a particular position
        ae(s,i+2*n,0x3f3f3f3f,0);
        ae(i+0*n,i+2*n,0x3f3f3f3f,0);
        ae(i+1*n,i+2*n,0x3f3f3f3f,0);
        ae(i+2*n,i+3*n,1,1);
        ae(i+3*n,T,0x3f3f3f3f,0);

        for(int j=i+1;j<=n;j++)if(num[i]-num[j]==1){ae(i+3*n,j+1*n,0x3f3f3f3f,0);break;}
        for(int j=i+1;j<=n;j++)if(num[j]-num[i]==1){ae(i+3*n,j+1*n,0x3f3f3f3f,0);break;}
        for(int j=i+1;j<=n;j++)if(num[i]%7==num[j]%7){ae(i+3*n,j+0*n,0x3f3f3f3f,0);break;}

        for(int j=i+1;j<=n;j++)if(num[i]%7==num[j]%7){ae(i+0*n,j+0*n,0x3f3f3f3f,0);break;}
        for(int j=i+1;j<=n;j++)if(num[i]==num[j]){ae(i+1*n,j+1*n,0x3f3f3f3f,0);break;}
    }
    while(SPFA());
    printf("%d\n",cost);
    return 0;
}