新疆大学ACM-ICPC程序设计竞赛五月月赛(同步赛)

链接： https://www.nowcoder.com/acm/contest/116/C 来源：牛客网 杨老师认为他的学习能力曲线是一个拱形。勤奋的他根据时间的先后顺序罗列了一个学习清单，共有n个知识点。但是清单中的知识并不是一定要学习的，可以在不改变先后顺序的情况下有选择的进行学习，而每一个知识点都对应一个难度值。杨老师希望，后学习的知识点的难度一定不低于前一个知识点的难度（i<j时ai<=aj），而可能存在一个临界点，在临界点以后，他希望后学习的知识点的难度一定不高于前一个知识点的难度（i<j时ai>=aj）。杨老师想尽可能多的学习知识。请问：杨老师最多可以学习多少知识？

输入描述:

第一行：一个整数n（0<n<500000）接下来一行：n个整数，第i个整数ai（0<=ai<500000）表示第i道题目的难度。

输出描述:

一行一个整数，表示杨老师最多可以学习多少个知识。

输入

5 1 4 2 5 1

输出

4

思路：题目要求是先找到一个非递减序列（即i<j时ai<=aj）,然后再找一个非递增序列(即i>j时ai<=aj)，由此我们可以想到我们先找一个单调递增序列然后再找一个单调递减序列，我们可以在找第二个序列的时候可以从原序列倒着找，这样就相当于找两个单调递增子序列。然后再对应相加减一即为结果(减一是因为最终结果序列的最大值用了两遍）。

样例:         1 4 2 5 1

第一个序列:1 2 2 3 3

第二个序列:2 3 2 2 1

结果序列:  3 5 4 5 4

代码:

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define INF 0x3f3f3f using namespace std; ll a[500010],b[500010],c1[500010],c2[500010]; ll dp1[500010],dp2[500010]; ll n; void LCIS(ll c[],ll num[],ll dp[]) { ll len=0; for(int i=1;i<=n;i++) { ll j=upper_bound(c+1,c+1+len,num[i])-c; c[j]=num[i]; dp[i]=j; len=max(len,j); } } int main() { while(scanf("%lld",&n)!=EOF) { for(int i=1,j=n;i<=n;j--,i++) { scanf("%lld",&a[i]); b[j]=a[i]; c1[i]=c2[i]=INF; } memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); // printf("##\n"); LCIS(c1,a,dp1); LCIS(c2,b,dp2); ll ans=0; for(int i=1;i<=n;i++) { ans=max(ans,dp1[i]+dp2[n-i+1]-1); } printf("%lld\n",ans); } return 0; }