1264：【例9.8】合唱队形

http://ybt.ssoier.cn:8088/problem_show.php?pid=1264

题目的实质实际上是一个双向LIS,对于每一个点和最大值进行一个比较，求得最大值。

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 ll n,maxn;
 5 const ll N=520;
 6 ll dp[N],a[N],len[N],k,dp2[N];
 7 int main()
 8 {
 9     scanf("%lld",&n);
10     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
11     k=0;
12     for(int i=1;i<=n;i++)
13     {
14         ll l=0,r=k;
15         while(l<r)
16         {
17             ll mid=l+r+1>>1;
18             if(dp[mid]mid;
19             else r=mid-1;    
20         }    
21         k=max(k,r+1);
22         len[i]=r+1;
23         dp[r+1]=a[i];
24     } 
25     k=0;
26     for(int i=n;i>=1;i--)
27     {
28         ll l=0,r=k;
29         while(l<r)
30         {
31             ll mid=l+r+1>>1;
32             if(dp2[mid]mid;
33             else r=mid-1;
34         }
35         k=max(k,r+1);
36         maxn=max(maxn,len[i]+r+1);
37         dp2[r+1]=a[i];
38     }
39     cout<1<<'\n';
40     return 0;
41 }