如果有m个人变成新的队形

HDU  4513

吉哥这两天对队形相比感兴趣。
  有一天,有n个人按顺序站在她的前方,他们的身体高度分别是h11, h22 …
hnn,吉哥愿意从中挑出部分人,让那些人形成贰个新的队形,新的队形若满意以下三点供给,则称之为完美队形:
  
  1、挑出的中国人民保险公司持他们在原队形的相对顺序不改变;
  2、左右对称,要是有m个人造成新的队形,则第1私人民居房和第m私有身体高度一样,第2私有和第m-1私有身体高度一样,就那样推算,当然,假若m是奇数,中间那个人能够私行;
  3、从左到中路那家伙,身体高度需确定保障递增,假若用H表示新队形的万丈,则H11
< H22 < H33 …. < Hmidmid。

Problem Description

  以后吉哥想精通:最多能选出多少人结合完美队形?

  吉哥又想出了贰个新的两全队形游戏!
  假若有n个人按顺序站在她的眼下,他们的身体高度分别是h[1], h[2] …
h[n],吉哥梦想从中挑出一些人,让这么些人形成二个新的队形,新的队形若满意以下三点须要,则正是新的体贴入妙队形:

Input

  第一行输入T,表示总共有T组数据(T <= 20);
  每组数据先输入原先队形的人数n(1<=n <=
200),接下去一行输入n个整数,表示按梯次从左到右原先队形地方站的人的身体高度(50
<= h <= 250,不拔除比不够高小和英豪的)。

  1、挑出的人维持原队形的相对顺序不改变,且必须都以在原队形中延续的;
  2、左右对称,倘诺有m个人造成新的队形,则第1私家和第m私家身体高度相同,第2私家和第m-1私人民居房身高一样,依此类推,当然假如m是奇数,中间那家伙能够率性;
  3、从左到中路那家伙,身体高度需保险不下滑,假诺用H表示新队形的万丈,则H[1]
<= H[2] <= H[3] …. <= H[mid]。

Output

  请输出能整合完美队形的最多少人口,每组数据输出占一行。

  未来吉哥想清楚:最多能选出几个人组成新的通盘队形呢?

Sample Input

2
3
51 52 51
4
51 52 52 51

Input

Sample Output

3
4

最长公共上涨自种类的变形。

  • 建立dp数组,dp[i]代表以a[i]这一个数为最大值组成完美队形的最多少人口。
  • 下一场就和后面包车型大巴LCIS同样,找四个变量更新小于a[i]澳门真人网上娱乐网址,的a[j]的dp[j]的最大值。只不过当前j的限量为[i,n].

    #include

    using namespace std;
    const int N = 1007;
    int n;
    int a[N], dp[N];

    void solve()
    {

    scanf("%d", &n);
    for(int i=1; i<=n; ++ i)
        scanf("%d", &a[i]);
    
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; ++ i)
    {
        int k = 0;
        for(int j=n; j>=i; -- j)
        {
            if(a[i] == a[j])
            {
                if(i < j)
                    dp[j] = max(dp[j], k + 2);
                else
                    dp[j] = max(dp[j], k + 1);
            }
            else if(a[i] > a[j] && dp[j] > k)
                k = dp[j];
        }
    }
    int ans = 0;
    for(int i=1; i<=n; ++ i)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
    

    }

    int main()
    {

    int t;
    scanf("%d", &t);
    for(int i=0; i<t; ++ i)
        solve();
    return 0;
    

    }

  输入数据第一行李包裹括贰个整数T,表示总共有T组测量检验数据(T <= 20);
  每组数据首先是多个整数n(1 <= n <=
一千00),表示原来队形的人头,接下去一行输入n个整数,表示原队形从左到右站的人的身体高度(50
<= h <= 250,不排除极其矮小和远大的)。

Output

  请输出能组成完美队形的最多个人口,每组输出占一行。

Sample Input

2 3 51 52 51 4 51 52 52 51

Sample Output

3 4

Source

二〇一二Tencent编制程序全程马拉松初赛第二场(一月二十五日)

Recommend

liuyiding   |   We have carefully selected several similar problems for
you:  5669 5668 5667 5666 5665 

 

题意:求最长的回文数列,且回文数列知足H[1] <= H[2] <= H[3]
…. <= H[mid];

 

思路:用int数组仿照字符数组,在各种数字之间插入0将数老板变为奇数,注意将边界设为多个抢先250的值;

 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
int n,p[N];
int s[2*N],str[2*N];

void kp()
{
    int mx=0;
    int id;
    for(int i=1; i<n; i++)
    {
        if(mx>i)
            p[i]=min(p[2*id-i],p[id]+id-i);
        else
            p[i]=1;
        for(; i+p[i]<n;)
        {
            ///cout<<6<<endl;
            if(str[i+p[i]]==str[i-p[i]])
            {
                if(str[i+p[i]]==0) p[i]++;
                else if(str[i+p[i]]<=str[i+p[i]-2])
                {
                    p[i]+=2;
                }
                else break;
            }
            else break;
        }
        ///for( ;str[i+p[i]]==str[i-p[i]];p[i]++);
        if(p[i]+i>mx)
        {
            mx=p[i]+i;
            id=i;
        }
    }
}

void init()
{
    str[0]=0;
    str[1]=0;
    for(int i=0; i<n; i++)
    {
        str[i*2+2]=s[i];
        str[i*2+3]=0;
    }
    n=n*2+2;
    ///s[n]=0;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&s[i]);
        init();
        kp();
        int ans=0;
        for(int i=1; i<n; i++)
            if(p[i]>ans)
                ans=p[i];
        printf("%d\n",ans-1);
    }
    return 0;
}