题解 P4310 【绝世好题】

· · 题解

绝对好题

Solution

　　这道题目的九十分做法非常好做, 然而我用一种非常鬼畜的思路A了过去, 而且只用了44ms.

　　先介绍一下90分做法, 用\textbf{f(i)}表示前\text{i}个数产生的最长不互斥子序列的元素个数, 如果\text{a}_i\ \vee \text{a}_{i-1}>0, 那么前i个数的最长不互斥子序列就可以由前i-1个数的最长不互斥子序列加上第i个数得到, 即

f(i)=\max f(j)+1,j<i\ and\ a_i\vee a_{i-1}>0

所以这是一个所有人都可以想到的转移, 但是只能得到90分.

　　其实每次都枚举一遍j是非常浪费时间的, 而且我们知道f(i)的值为f(k)+1, 每次枚举j就是为了找到这个k, 所以我们很可能在某个时候已经找到了这个k但是我们还在继续枚举j, 所以我就可以记录一下\max f(j), 因为f(i)的值不会超过\max f[j]+1, 所以在更新f(i)为\max f(j)+1后就退出枚举就好了.

　　只是没想到这样做的效果那么好, 竟然直接通过了…….

Code

#include<cstdio>
#define N 200005

int max(int i,int j){
    return i>j?i:j;
}

int n;
int s[N];
int f[N];
int ma[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&s[i]);
    for(int i=1;i<=n;++i)f[i]=1;
    for(int i=1;i<=n;++i){
        for(int j=i-1;j;--j){
            if(f[i]>ma[i-1])break;
            if(s[i]&s[j])f[i]=max(f[i],f[j]+1);
        }
        ma[i]=max(ma[i-1],f[i]);
    }
    printf("%d",ma[n]);
    return 0;
}