sdnu1395(双向LIS)

Problem B: Trainsorting   ( LIS)
Description
        
        
            
Problem B: Trainsorting
Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.
Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.
Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.
Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?


Input

The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.  


Output


Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.


Sample Input

3
1
2
3


Sample Output
3

求满足题意的火车最长长度,求正序和反序的LIS,相加减1即可。

#include <bits/stdc++.h>
using namespace std;

int dp1[2005],dp2[2005],a[2005];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n)
        {
            cout<<0<<'\n';
            continue;
        }
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        int ans=0;
        for(int i=n;i>=1;--i)
        {
            dp1[i]=1;
            dp2[i]=1;
            for(int j=n;j>i;--j)
            {
                if(a[j]<a[i])
                    dp1[i]=max(dp1[i],dp1[j]+1);
                if(a[j]>a[i])
                    dp2[i]=max(dp2[i],dp2[j]+1);
            }
            ans=max(ans,dp1[i]+dp2[i]-1);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

 

全部评论

相关推荐

06-27 15:15
长安大学 Java
哈哈哈,你是老六:这种就是培训机构骗钱的
点赞 评论 收藏
分享
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务