动态规划详解
2025-12-28 18:18:32
发布于：广东
10阅读
0回复
0点赞
//动态规划
//记忆化
#include<bits/stdc++.h>
using namespace std;
int a[10020];
int ans[10020];
//ans[i] ---->>前i并且a[i]作为尾项子序列,的最长上升子序列长度,答案存放在ans[i];
//ans[i]=max(ans[1-i])+1,1;
//状态转移方程
//N*N
//树状数组
// low_bit()
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int mx=0;
for(int i=1;i<=n;i++){
ans[i]=1;//
for(int j=1;j<i;j++){
if(a[i]>a[j]){
ans[i]=max(ans[i],ans[j]+1);
}
}
mx=max(mx,ans[i]);
}
cout<<mx<<endl;
}
//状态转移方程式
//
这里空空如也
有帮助，赞一个