題意：
n個數，要求取得最多的數，使得任意兩個數其中一個為另一個倍數，
思路：
則定義
d
p
[
i
]
dp[i]
dp[i]為第i個數為取出序列數中最大數時，最多取多少數，
則
d
p
[
i
]
dp[i]
dp[i]向
i
?
2
,
i
?
3
,
i
?
4...
i*2,i*3,i*4...
i?2,i?3,i?4...轉移，復雜度1e7log
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int maxm = 1e7 + 7;
int a[maxn];
int vis[maxm];
int dp[maxm];
int main() {
int n;scanf("%d",&n);
vector<int>vec;
int mx = 0;
for(int i = 1;i <= n;i++) {
int x;scanf("%d",&x);
vec.push_back(x);
mx = max(mx,x);
vis[x]++;
}
int ans = 0;
for(int i = 1;i <= mx;i++) {
dp[i] = vis[i];
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i = 0;i < vec.size();i++) {
ll num = vec[i];
for(int j = 2;j <= maxm;j++) {
num += vec[i];
if(num > mx) break;
if(!vis[num]) continue;
dp[num] = max(dp[num],vis[num] + dp[vec[i]]);
}
}
for(int i = 1;i <= mx;i++) {
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/193746.html
標籤：java
上一篇：Problem B: DFS or BFS? 廣度優先搜索應用
下一篇：猴子選大王（Java）