中山做网站企业,购物网站页面设计思路,网站做收录,做公众号还是网站题目描述 小明是蓝桥王国的骑士#xff0c;他喜欢不断突破自我。 这天蓝桥国王给他安排了 N 个对手#xff0c;他们的战力值分别为 a_1,a_2,…,a_n#xff0c;且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战#xff0c;也可以选择避战。 身为高傲的骑士#xff… 题目描述 小明是蓝桥王国的骑士他喜欢不断突破自我。 这天蓝桥国王给他安排了 N 个对手他们的战力值分别为 a_1,a_2,…,a_n且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战也可以选择避战。 身为高傲的骑士小明从不走回头路且只愿意挑战战力值越来越高的对手。 请你算算小明最多会挑战多少名对手。 输入描述 输入第一行包含一个整数 N表示对手的个数。 第二行包含 N 个整数 a_1,a_2,…,a_n分别表示对手的战力值。 输出描述 输出仅一行包含一个整数表示答案。 样例输入 6 1 4 2 2 5 6 样例输出 4 思路本来是想用LIS动态规划来做的但是不出意外超时了LIS代码如下
#includebits/stdc.h
using namespace std;
int dp[400010];
int a[400010];
int main(){int n;cinn;for(int i1;in;i){cina[i];}for(int i1;in;i){for(int j0;ji;j){if(a[i]a[j])dp[i]max(dp[i],dp[j]1);}}int maxN0;for(int i1;in;i){if(maxNdp[i])maxNdp[i];}coutmaxNendl;
}
那怎么改进呢比如说1 4 2 2长度为2的子序列是不是有{1,4}和{1,2}如果以后出现一个数字5LIS的做法是遍历1 4 2 2所有数字的值并dp出把5放进哪个子序列它形成的序列最长。很明显是{1,4,5}或者{1,2,5}但是细想一下{1,4}跟{1,2}的长度是一样的比4大的数字一定比2大比2大的数字不一定比4大那在长度一样的时候我维护一个最小值就好了用那个最小值来形成进一步的子序列。
代码如下slln[i]k表示长度i的子序列中末尾的最小值是k
#includebits/stdc.h
using namespace std;
int a[400010];
int slln[400010];
int main(){int n;cinn;for(int i1;in;i){cina[i];}memset(slln,0x3f3f3f3f,sizeof(slln));slln[0]0;int len1;for(int i1;in;i){for(int jlen-1;j0;j--){if(slln[j]a[i]){slln[j1]min(slln[j1],a[i]);if(j1len)len;break;}}}coutlen-1endl;
}
