小信的装备RE30

问题讨论区 普及段
21

image

我请问我写的不是跟你一样吗？ @charlieqi

1 个赞
22

loglog1e7才4跟常数没区别

23

过来救我！！！

1 个赞
24

最后用欧拉筛的框架套DP即可！

1 个赞
25

不用筛，直接dp就行了
dp[i]代表i为最大值的时候能够构成的最大序列长度

26

不行，需要筛

27

这样有超时的风险，虽然能过

28

我直接dpac了

29

其实可以专门出数据卡掉的

30

显然，你这不是正解

31

替他回复一下，他被禁言了 :sleepy:

32

你现在的代码长啥样，啥状态，重新发一下

33

谁被禁言了

34 
#include <bits/stdc++.h>
#define s i*prime[j]
using namespace std;
map<int,int> mp;
map<int,int> vis;
int prime[10000001],dp[10000001];// dp[i]->当前选的是i的因数且可选,最多能选多少个数
int main(){
	freopen("item.in","r",stdin);
	freopen("item.out","w",stdout);
	int n,pmaxn=0;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		mp[x]++;
		pmaxn=max(pmaxn,x);
	}
	int p=0;
    vis[0]=1;
    vis[1]=1;
    int q=sqrt(n);
    for(int i=2;i<=q;i++){
        if(vis[i]==0){
            for(int j=i+i;j<=n;j+=i){
                vis[j]=1;
            }
        }
    }
    for(int i=1;i<=pmaxn;i++){
      if(vis[i]==0){
        prime[++p]=i;
      }
    }
	for(int i=1;i<=pmaxn;i++){
		dp[i]+=mp[i];
		for(int j=1;s<=pmaxn&&j<=p;j++){
			dp[s]=max(dp[s],dp[i]);
		}
	}
	int maxn=0;
	for(int i=1;i<=pmaxn;i++){
		if(mp[i]!=0){
			maxn=max(maxn,dp[i]);
		}
	}
	printf("%d",maxn);
}
/*
6
1 4 2 8 5 7

1 2 3 2 2 4
1 2 4 5 7 8
*/

RE 30，换了埃拉托斯尼筛

35

@杨思越 人呢？

36

埃氏筛时间复杂度太劣啦

37

不是你说让他用的吗？

38

我说他写的埃氏筛时间复杂度太劣啦，最优应该是ii<=q,j=ii

1 个赞
39

确实

40

唉，不是，markd什么东西？

1 个赞