阿里云 网站部署,网站建设v5star,79招商创业网,做网站前的准备什么分析#xff1a; 定义状态dp[i]表示长度为i的最长不下降子序列最大的那个数。 每次进来一个数直接找到dp数组第一个大于于它的数dp[x]#xff0c;并把dp[x - 1]修改成 那个数。就可以了 AC代码#xff1a; # include iostream
# include cstdio
# include 定义状态dp[i]表示长度为i的最长不下降子序列最大的那个数。 每次进来一个数直接找到dp数组第一个大于于它的数dp[x]并把dp[x - 1]修改成 那个数。就可以了 AC代码 # include iostream
# include cstdio
# include cstring
# include algorithm
using namespace std;
const int N 100012;
int dp[N],n,pre[N],x,y,xh[N],a[N];
void out(int k){if(k)out(pre[k]);else return;printf(%d ,a[k]);
}
int main(){memset(dp,0x3f3f3f3f,sizeof dp);for(int i 1;i n;i){scanf(%d,a[i]);y upper_bound(dp 1,dp n 1,a[i]) - dp;dp[y] a[i];xh[y] i;pre[i] xh[y - 1]; }int len lower_bound(dp 1,dp n 1,dp[0]) - dp - 1;printf(%d\n,len);out(xh[len]);return 0;
} 转载于:https://www.cnblogs.com/lzdhydzzh/p/7673831.html
