题目链接在这里：链接
对于这一道题其实主要思想当然是dp了，不过有个问题那就是dp的时候不容易找到dp前的下标所以可以想到的办法利用一个新数组存储下标（ptr数组），dp数组另做处理，这样双线并行即可。
而对于本题来说，主要思路当然是找到对于a[i]来说的在j=（1，i-1）最近且最长子序列，子序列满足的条件为a[m]%(a[m-1]-1)==0（当然前提条件是事先对数组进行了排序）那么状态转移方程就变成了
**ans[i]=max(ans[i],ans[j]+1)**
不过可惜的是这样的复杂度是O（n2），显然太大了，需要寻求优化
接下来想如何达到最好的优化，不难想到a[j]必然是a[i]的因子，所以直接在a[i]的因子里寻找合适的k=a[j],同时a[i]%k=0，那么复杂度就变成了O（n*sqrt（n））；复杂度直线下降，那么怎么寻找合适的k呢，这就需要用到前面说的ptr下标数组了（前提条件也很明确：不会出现重复的数字），下面是代码：
#include<cstdio>
#include<algorithm>
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int MAX_N=2e5+10;
int main(){
int t;scanf("%d",&t);while(t--){
int n,i,a[MAX_N],ans[MAX_N]={
0},p[MAX_N]={
0};//a数组用来存输入,ans数组用于dp找下标//p数组即为ptr指针用来存储一直下标的j的地址 int MAX=0,ma;if(n==1){
printf("0\n");continue;}scanf("%d",&n);for(i=1;i<=n;i++){
scanf("%d",&a[i]);}sort(a+1,a+n+1);//排序当然是必要的啦 int ptr=1;for(i=1;i<=n;i++){
ans[i]=1;for(int j=1;j*j<=a[i];j++){
if(a[i]%j!=0){
continue;}ptr=a[i]/j;//先暂存一下下标地址ans[i]=max(max(ans[i],ans[p[j]]+1),ans[p[ptr]]+1);}p[a[i]]=i;MAX=max(MAX,ans[i]);
//此处的MAX即为这个数组中出现beatiful number的最大值 }printf("%d\n",n-MAX); }return 0;
}
一切结束，题目不难就是有一点点费脑筋，思路很重要。