问题标题: 酷町堂：救救孩子吧，孩子快疯了

#include <bits/stdc++.h>
using namespace std;

const int N=3e6+5;

int n, a[N], dp[N], ans;

inline int max(int x, int y) {
	return x>y ? x : y;
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%d", &a[i]);
	}
	
	for(int i=1; i<=n; i++) {
		dp[i]=1;
		for(int j=1; j<i; j++) {
			if(a[j]%a[i]==0 || a[i]%a[j]==0)
				dp[i]=max(dp[i], dp[j]+1);
		}
	}
	
	printf("%d", dp[n]);
	return 0;
}

如何降为O(n)???

5608  5608  5608  5608  5608  5608  5608

2020合肥市赛 传送门

e的x次幂在2021-08-08 13:24:40追加了内容

顶