【DP】【GG选题】

【题目来源】http://acm.buaa.edu.cn/problem/431/

【题目分析】F[K]表示前I个位置，末尾数字包含因子K的那个长度最长的序列所含题目的个数。（有点绕）举例进行分析：4 6 9 12

　　　　　　初始化为F数组为0；

　　　　　　4=2*2，只含1个因子2，F[2]+=1,此时F[2]=1；

　　　　　　6=2*3，含有2个因子2和3，F[2]+=1，F[3]+=1，此时F[2]=2，F[3]=1，max{F[2],F[3]}= 2,所以将F[3]=2；

　　　　　　9=3*3，只含1个因子3，F[3]+=1，此时F[3]=3;

　　　　　　12=2*2*3,含有2个因子2和3，F[2]+=1，F[3]+=1，此时F[2]=3，F[3]=4，max{F[2],F[3]}=4，所以将F[2]=4；

　　　　　输出4

　　　　　　以上的过程重在强调一件事情，当前这个数所包含的因子可以作为以后的扩展。

【代码如下】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 #define rep(i, x) for (int i = 1; i <= x; i ++)
 6 
 7 //#define FILE_IO
 8 
 9 using namespace std;
10 
11 int T, N, B[18], F[100001], Ans = 1;
12 
13 void Clear()
14 {
15     memset(F, 0, sizeof(F));
16     Ans = 1;
17 }
18 
19 void Get(int k)
20 {
21     int l = 0, i = 2;
22     while (i * i <= k)
23     {
24         if (k % i == 0)
25         {
26             B[++ l] = i;
27             do { k /= i; } while (k % i == 0);
28         }
29         i ++;
30     }
31     if (k > 1) B[++ l] = k;
32     int tmp = 0;
33     for (int i = 1; i <= l; i ++)
34     {
35         F[B[i]] ++;
36         tmp = max(tmp, F[B[i]]);
37     }
38     for (int i = 1; i <= l; i ++) F[B[i]] = tmp;
39     Ans = max(Ans, tmp);
40 }
41 
42 void Solve()
43 {
44     scanf("%d", &N);
45     rep(i, N)
46     {
47         int a; scanf("%d", &a);
48         Get(a);
49     }
50 }
51 
52 int main()
53 {
54     #ifdef FILE_IO
55     freopen("Dp.in", "r", stdin);
56     #endif // FILE_IO
57     scanf("%d", &T);
58     rep(i, T)
59     {
60         Solve();
61         printf("%d\n", Ans);
62         Clear();
63     }
64     return 0;
65 }