Codeforces

分析

设 $f_{i, j}$ 表示第一段到了 $i$，第二段到了 $j$ 的最大长度。容易写出 $\mathcal{O}(n^3)$ 的 DP。

考虑优化。设 $maxmod_k$ 表示最大的满足 $a_j\equiv k\pmod 7$ 的 $f_{i, j}$，$maxnum_k$表示最大的满足 $a_j = k$ 的 $f_{i, j}$。于是转移变为
$$
f_{i, j}=\max\left\{f_{i, 0}, maxmod_{a[j] \bmod 7}, maxnum_{a_j - 1}, maxnum_{a_j + 1}\right\} + 1
$$
每次计算出当前 DP 值后更新以上两个数组即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=5000+10;

int n,ans;
int a[MAXN];
int f[MAXN][MAXN];
int maxmod[8],maxnum[100001];

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=0;i<=n;++i) {
        memset(maxmod,0,sizeof(maxmod));
        memset(maxnum,0,sizeof(maxnum));
        for (re int j=1;j<=i;++j) {
            chkmax(maxmod[a[j]%7],f[i][j]);
            chkmax(maxnum[a[j]],f[i][j]);
        }
        for (re int j=i+1;j<=n;++j) {
            chkmax(f[i][j],f[i][0]+1);
            chkmax(f[i][j],maxmod[a[j]%7]+1);
            chkmax(f[i][j],maxnum[a[j]-1]+1);
            chkmax(f[i][j],maxnum[a[j]+1]+1);
            chkmax(maxmod[a[j]%7],f[i][j]);
            chkmax(maxnum[a[j]],f[i][j]);
            chkmax(ans,f[j][i]=f[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}