【递推】BZOJ 4300:绝世好题

4300: 绝世好题

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 564 Solved: 289
[Submit][Status][Discuss]

Description

给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。

Input

输入文件共2行。

第一行包括一个整数n。

第二行包括n个整数，第i个整数表示ai。

Output

输出文件共一行。

包括一个整数，表示子序列bi的最长长度。

Sample Input

3
1 2 3

Sample Output

HINT

对于100%的数据，1<=n<=100000，ai<=10^9。

　　刚考完联赛回家搞了一个星期常规=- =

　　然后老师叫我们还是要保持一下手感的是吧

　　然后随便找了一道水题。。

　　貌似是单调DP？

　　发现不行

　　然后想了一下按位单调DP

　　感觉好像可以但不是最优解。。

　　看了一下status

　　发现最短的代码400b左右

　　貌似不是单调DP？

　　然后查了一下。。

　　f[j]代表第j位的最优值

　　之后每次更新一个数每一位的最优值为所有位的f值+1即可。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define maxn 100001

 using namespace std;

 int a[maxn],f[maxn];

 inline int in()

 {

     int x=;char ch=getchar();

     while(ch<''||ch>'')ch=getchar();

     while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();

     return x;

 }

 int main()

 {

     int n;

     n=in();

     for(int i=;i<=n;i++)a[i]=in();

     for(int i=;i<=n;i++)

     {

         int cal=;

         for(int j=;j<=;j++)if(a[i] & (<<j))cal=max(cal,f[j]+);

         for(int j=;j<=;j++)if(a[i] & (<<j))f[j]=cal;

     }

     int ans=;

     for(int j=;j<=;j++)ans=max(ans,f[j]);

     printf("%d",ans);

     return ;

 }

秒客网