CF 264B(序列的重叠)

D. Good Sequences
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output
数列 n 有 a1, a2, ..., an 个数（严格递增），请从中任意删去一些数，使序列相邻2数都不互质。
问删后序列最长长度.
Input
第一行 n (1 ≤ n ≤ 105) 第二行序列 a1, a2, ..., an (1 ≤ ai ≤ 105; ai < ai + 1).
Output
删后序列最长长度.
Sample test(s)
input
5
2 3 4 6 9
output
4
input
9
1 2 3 5 6 7 8 9 10
output
4
Note
In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.
 
枚举开头即可。
[cpp]  
#include<cstdio>  
#include<iostream>  
#include<cstdlib>  
#include<cstring>  
#include<cmath>  
#include<functional>  
#include<algorithm>  
#include<cctype>  
using namespace std;  
#define MAXN (100000+10)  
int n,a[MAXN];  
bool b[MAXN]={0};  
int 易做图(int a,int b){return (b==0)?a:易做图(b,a%b);};  
int main()  
{  
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);  
    int ans=0;  
    for (int i=1;i<=n;i++)  
    if (!b[i])  
    {  
        int len=1;  
        b[i]=1;  
        int head=i,tail=i+1;  
        while (tail<=n)  
        {  
            if (易做图(a[tail],a[head])==1) tail++;  
            else {b[head]=1;head=tail;tail++;len++; }  
        }  
        ans=max(ans,len);  
    }  
    cout<<ans<<endl;  
          
    return 0;  
}  

补充：综合编程 , 其他综合 ,

上一个：Introduction to SEO Search Engine Optimisation practices
下一个：位运算