PAT 1059 Perfect Sequence (25)（dp完美序列）

序列）"/>

PAT 1059 Perfect Sequence (25)（dp完美序列）

题目

1059 Perfect Sequence (25)

解题思路

• 1.先排序然后找出每个点的最大长度。
• 2.对于起点i，假设循环找到的最后一个满足条件的位置 j >= i,那么对于起点为 i+1 ，j也会满足，例如排好序后序列为：1 2 3 4 5 6 7 8 9 20,p = 8,对于i = 0,那么最后一个满足条件的位置为 i = 7,即数字8,那么对于起点为 i+1,显然a[i + 1] * p = 2 * 8 > a[j] = 8也满足，则i+1可以直接从j开始考虑了。
• 3.注意如果是乘以p，则结果可能会溢出。

代码

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;
int n,p;
int main(){cin >> n >> p;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}sort(a.begin(),a.end());vector<int> b(n,0);int pre= 0,maxlen = 0;//找每个点的最大长度b[i],一直更新for (int i = 0; i < n; ++i) {//每个点又可以从前一个点找到了的位置pre开始找for (int j = max(i,pre); j < n; ++j) {if((double)a[j]/(double)p <= a[i]){b[i] = j - i + 1;pre = j;}else{break;}}//找到最大值maxlen = max(maxlen,b[i]);}cout<<maxlen<<endl;return 0;
}