4.【GDKOI2004】香樟树（camphor）
题目描述
被誉为江南四大名木之一的香樟树很有特色，它的树皮粗糙，质地却很均匀，从来没有白杨树的斑斑驳驳、没有柳树的肿瘤结节；树枝树干一分为二、二分为四一路长去，不会偷工减料也不会画蛇添足；树冠的形态是球形的，在天空中画出优美的曲线。 除了上述优点之外，香樟树还有一个秘密武器。那就是……………………它凭借朴实、厚重的优秀品格赢得了小狐狸的青睐！！！ 话说有一天，小狐狸正在湖边散步，忽然一阵风吹来，她赶紧闭上眼睛。当她再次睁开眼睛时，发现美丽的湖畔多出了一排整齐的香樟树。小狐狸非常兴奋，她对每棵树都观察入微，并且数出了它们的叶子个数。她觉得如果相邻两棵树的叶子个数互素是不和谐的。因此小狐狸想从一排香樟树中选出若干棵，在满足相邻两棵树的叶子个数不互素的条件下，使得树尽量多。
输入
第一行一个正整数n，表示有n棵香樟树。 第二行n个正整数，第i个数表示第i棵香樟树叶子的个数。
输出
一个正整数，表示最多能选多少棵树。
样例输入
6
6 2 3 15 8 5
样例输出
4
数据范围限制
对于60%的数据n<=1000
对于100%的数据 n<=100000，叶子个数<=100000
注意：选中的树不能改变其位置，即如果选中第(t1，t2，t3……tn)棵树 ，其中t1<t2<t3<……<tn则认为ti与ti+1相邻。
提示
选择第1、第3、第4和第6棵树
正解
很容易想到dp的做法，找出一个最长相邻不互素的序列
不优化dp代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[100005],f[100005];
bool gcd(int x,int y)//判断是否互素
{
int z;
while(x%y!=0)
{
z=y;
y=x%y;
x=z;
}
if(y>1)return true;
else return false;
}
int main()
{
freopen("camphor.in","r",stdin);
freopen("camphor.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=1;//本身
for(int j=1;j<=i-1;j++)//dp
if(gcd(a[i],a[j]))f[i]=max(f[i],f[j]+1);//不互素就比较
m=max(m,f[i]);
}
printf("%d",m);
return 0;
}
但是这样还会超时，所以我们要加个玄学优化，log
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[100005],f[100005];
int log(int x)//玄学log优化
{
int y=0;
while(x) x/=2,y++;
return y;
}
bool gcd(int x,int y)//判断是否互素
{
int z;
while(x%y!=0)
{
z=y;
y=x%y;
x=z;
}
if(y>1)return true;
else return false;
}
int main()
{
freopen("camphor.in","r",stdin);
freopen("camphor.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=1;//初值
for(int j=i-log(i)*2;j<=i-1;j++)//dp
if(j>0)if(gcd(a[i],a[j]))f[i]=max(f[i],f[j]+1);//先判断j是否>0，然后再dp比较
m=max(m,f[i]);
}
printf("%d",m);
return 0;
}
下面附本次比赛的其它题目
2020.03.18模拟赛18（第一题）
2020.03.18模拟赛18（第二题）
2020.03.18模拟赛18（第三题）
2020.03.18模拟赛18（第四题）
2020.03.18模拟赛18（总结）
京公网安备 11010502036488号