NC221203. 小圆前辈的数组Ⅱ
描述
在你的帮助下，小圆前辈成功破译了这个长为n的数组。原来这个数组是小焰同学上周送给她的，并安排小圆前辈帮她算出数组中的最长完美子序列的长度，可是粗心的小圆前辈忘记了。小圆前辈现在再一个一个找已经来不及了，于是便求助于你，你能帮她算出最长完美子序列的长度吗？
我们定义一个序列是完美的：对于所有的，满足b[i]不是b[i + 1]的因数。
输入描述
第一行只有三个整数n。
第一行共n个整数a[1]~a[n]。
输出描述
一个整形数表示答案。
示例1
输入:
6 1 2 3 1 2 1
输出:
4
说明:
可以取出索引为2，3，5，6的子序列：2 3 2 1
满足前一项不是后一项的因数，且长度为4，无法找到更长满足条件的子序列
C++(clang++11) 解法, 执行用时: 28ms, 内存消耗: 1764K, 提交时间: 2021-04-24 19:58:46
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+3;
int n,s[N],dp[N];
int k[N];
int main()
{
cin>>n;
int Max= 0;
for (int i=1;i<=n;i++)
{
cin>>s[i];
dp[i] = 1;
for (int j=i-1;j>=1; j--)
{
if(s[i]%s[j]!=0)
{
dp[i] = max(dp[i],dp[j]+1);
if(dp[j]==k[j])
break;
}
}
if(Max<dp[i])
Max=dp[i];
k[i] = Max;
}
cout<<k[n]<<endl;
return 0;
}