M_sea

CF813D Two Melodies
CodeForcesLuogu题意菊开写的:给一个长度为$n$的序列,求两个不相交的子集长度之和最大是多少。能放入...
扫描右侧二维码阅读全文
09
2019/01

CF813D Two Melodies

CodeForces

Luogu

题意

菊开写的:

给一个长度为$n$的序列,求两个不相交的子集长度之和最大是多少。能放入同一子集的条件是首先顺序不能变,然后每一个相邻的要么相差$1$或者相差$7$的倍数。

分析

设$f[i][j]$表示第一段到了$i$,第二段到了$j$的最大长度。容易写出$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]\%7],maxnum[a[j]-1],maxnum[a[j]+1]\right\}+1$。

每次计算出一个dp值都要更新$maxmod$和$maxnum$。

还有,可以只计算$j>i$的dp值,计算完后再将$f[i][j]$赋值给$f[j][i]$。

时间复杂度是$O(n^2)$的。

代码

//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;
}
最后修改:2019 年 01 月 23 日 01 : 01 PM

发表评论