本文共 1223 字,大约阅读时间需要 4 分钟。
最长上升子序列问题:
定义dp[i]:以 a[i]为末尾的 最长上升子序列 的长度。
递推关系:
dp[i]=max{1,dp[j]+1} 当 i>j且a[i]>a[j]时边界控制:
d[i]=1;#include#include #include #include using namespace std;int dp[100010];int a[100010];int main(){ int N; while (scanf("%d",&N)!=EOF) { int ans = 0; for (int i = 0; i < N; i++) scanf("%d", &a[i]); for (int i = 0; i < N; i++) { dp[i] = 1; for (int j = 0; j < i; j++) if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i]); } printf("%d\n", ans); }}
优化:
dp[i]:长度为i+1(数组从0存放)的 上升子序列中 末尾元素的最小值,不存在的话就是INF;边界控制:dp[i]=INF;
dp[i]=min(dp[i],a[j]) i=0或者dp[i-1]
#include#include #include #include #define INF 0x3f3f3f3fusing namespace std;int dp[100010];int a[100010];int main(){ int N; while (scanf("%d", &N) != EOF) { int ans = 0; for (int i = 0; i < N; i++) scanf("%d", &a[i]); fill(dp, dp + N, INF); for (int i = 0; i < N; i++) *lower_bound(dp, dp + N, a[i]) = a[i]; printf("%d\n", lower_bound(dp,dp+N,INF)-dp); }}
转载地址:http://mkyci.baihongyu.com/