MYF

Codeforces 264B Good Sequences

Posted on | In | | Visitors

题目链接

codeforces 264B

解题方法：DP

题目分析

题目大意

给出n个数，找出一个子序列，子序列中相邻两个的gcd不为1，求子序列的最大长度

解析

一开始妄想用DFS做，然而会T的很惨，看了看网上的解析，觉得McFlury说的不错，其实就是找出来所有的因子，用所有的因子将这些数连接起来，每次找出来当前数的一个因子，并且这个因子的dp值最大，用这个因子的dp值更新其他所有因子的dp值，以此处理这个数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 100005
int a[maxn];
int dp[maxn];
vector<int>t[maxn];
int main(){
    int n,ans=0,tmp;
    for (int i=2; i<maxn; i++) {
        for (int j=i; j<maxn; j+=i) {
            t[j].push_back(i);
        }
    }
    while (cin>>n) {
        ans=1;
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=n; i++) {
            cin>>tmp;
            int mx=1;
            for (vector<int>::iterator it=t[tmp].begin(); it!=t[tmp].end(); it++) {
                mx=max(mx, dp[*it]+1);
            }
            for (vector<int>::iterator it=t[tmp].begin(); it!=t[tmp].end(); it++) {
                dp[*it]=max(dp[*it], mx);
            }
        }
        for (int i=0; i<maxn; i++) {
            ans=max(ans, dp[i]);
        }
        cout<<ans<<endl;
    }
}