解题报告:dp+数论

解题报告:

传送门!

开始看这题的时候想挂了,,,想了个显然是错解的想法,,,就是,我也不知道我怎么想的,鬼迷心窍地就想开个数组存每个质因数的倍数的出现次数,然后排下序的max就是ans了,,,显然的一个错解,但是其实给正解提供了一点点启发

还是先说一个对正解毫无启发的暴力趴

就是个最简单的dp,当做最长上升子序列这种做,n²转移即可

显然是过不了的

然后我们既然想到最长上升子序列了,就应该能想起,那种题目其实可以二分然后O(nlogn)地过去,举一反三一下,这题484也能优化到O(nlogn) (其实只是凑巧希望不要误导了昂!和二分什么的毫无关系只是想到了就顺口提句QAQ复习下那个知识点QAQ

然后这时候就想起我最前面的那个想法,于是就想到,枚举质因数地转移,f[i]:第一个数是i的倍数的最长长度

有点像之前做过的,绝世好题(当然方法什么的显然不一样,但我jio得思想什么的其实是差不多的,都是O(n²)过不去所以从别的地方入手就能想到优化辣!

然后分享一个很烦躁的事儿,,,

就是,我开始自信满满地打完了代码

然后交上去,RE

然后花式改一直RE在一个地方

然后我就放弃了,照着题解改,A了

然后我再一点点改回来

最后改回了我最开始的代码

A了???

我耗了四五天:D

算了女孩子不能发脾气会长白头发的(假的x

放下代码,,,

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define rg register
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)const ll N=;
ll n,f[N],as=,a[N];inline int read()
{
    rg char ch=getchar();rg ll x=;rg bool y=;
    while(ch!='-' && (ch>'' || ch<''))ch=getchar();
    if(ch=='-')ch=getchar(),y=;
    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
    return y?x:-x;
}int main()
{
    n=read();
    while(n--)
    {
        ll x=read(),mx=f[x];
        for(rg ll i=;i*i<=x;i++)if(x%i==)mx=max(max(mx,f[i]),f[x/i]);
        for(rg ll i=;i*i<=x;i++)if(x%i==)f[i]=f[x/i]=mx+;f[x]=mx+;
        as=max(as,mx+);
    }
    printf("%d\n",as);
    return ;
}

upd:,,,我我我我知道我RE哪儿了

这样儿的,之前叶佬港压行的时候,就说,return 0,balabala;后面可以接很多动作,麻油关系

于是我就打了return 0,printf();

但是!printf会返回一堆乱码!

而return返回的是最后一个数值!

所以就会RE!

然后还因此被hl聚聚D辣QAQ