最长上升子序列dp法
#include<bits/stdc++.h> #define M 100005 using namespace std; int a[M]={0,389,207,155,300,299,170,158,65}; int dp[M]; int main(){ int len = 1,Max = 1; memset(dp,1,sizeof(dp));//初始化 for(int i = 2;i <= 8;i++){ //dp[i]表示以i结尾的最长子序列长度 for(int j = 1;j < i;++j){ if(a[j] < a[i]){ //枚举前i个比a[i]小的,作为倒数第二个,a[i]为第一个 dp[i] = max(dp[i],dp[j]+1); } } Max = max(Max,dp[i]) } cout<<len; return 0; }
最长递减子序列
#include<bits/stdc++.h> #define M 100005 using namespace std; int a[M]={0,389,207,155,300,299,170,158,65}; int dro[M]; int main() { int len=1; dro[1]=a[1];//初始化 for(int i=2;i<=8;i++){ if(a[i]>=dro[len]) {//找到dro中第一个比a[i]小的,替换 for(int j = 1;j <= len;++j){ if(dro[j] < a[i]){ dro[j] = a[i]; break ; } } } else dro[++len]=a[i]; } cout<<len; return 0; }