Longest Ordered Subsequence

0
11

这个嘛,我觉得是m[i]=max(m[0~i-1])+1;完了复杂度是O(n^2/2);

书上开了一个辅助数组d[],就很nice,思想是如果m[i]>d[最后一个],辣么直接添加进来,

如果m[i]<d[最后一个],就让它替换掉d[]中第一个比它大的,毕竟比它大的在前面,发展显然没有它好

当然也可以dp

代码嘛……

#include <algorithm>
#include <iostream>
using namespace std;
const int MAX = 1000;
int a[MAX],dp[MAX];
int main(){

int n,m=1;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];

for(int i = 0; i < n; i++) {
dp[i] = 1;
for(int j = 0; j < i; j++) {
if(a[j] < a[i] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
for(int i=0;i<n;i++){
m=(dp[i]>m)?dp[i]:m;
}
cout << m << endl;
return 0;
}

<

发布回复

请输入评论!
请输入你的名字