poj1836Alignment

发表于: 2013年02月09 00:00

题意大概是:最少去掉队列中的多少个士兵后,使队伍中的每个士兵都可以看见无穷远的地方

解法:LIS问题 这样我们从左向右和从右向左求最两次最长上升子序列.然后枚举每一个中间点.找到两个序列 和的最大值.这样出队伍的人也就确定了.

最长上升子序列的N^2算法

设dp[i]在序号为i的的串中,最长的上升子序列的长度.

那么已知dp[i]后,dp[i+1]…dp[n]的值也就显而易见

:::c++
//bnu1955
#include<stdio.h>
#include<string.h>
double ss[1005];
int s1[1005],s2[1005];
int n;
int max(int a,int b)
{
    return a>b?a:b;
}
int lis1() //最长上升子序列
{
    s1[0]=1;
    for(int i=0;i<n;i++)
    {
        if(!s1[i]) s1[i]=1;
        for(int j=i+1;j<n;j++)
        {
            if(ss[j]>ss[i] && s1[j]<s1[i]+1)
            {
                s1[j]=s1[i]+1;
            }
        }
    }
    for(int i=1;i<n;i++)
        s1[i]=s1[i-1]<s1[i]?s1[i]:s1[i-1];
}
int lis2()
{
    s2[n-1]=1;
    for(int i=n-1;i>0;i--)
    {
        if(!s2[i]) s2[i]=1;
        for(int j=i-1;j>=0;j--)
        {
            if(ss[j]>ss[i] && s2[j]<s2[i]+1)
            {
                s2[j]=s2[i]+1;
            }
        }
    }
    for(int i=n;i>0;i--)
        s2[i-1]=s2[i]>s2[i-1]?s2[i]:s2[i-1];
}
int sum()
{
    int max1=-1;
    for(int i=0;i<n;i++)
        max1=max(max1,s1[i]+s2[i+1]);
    return max1;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%lf",&ss[i]);
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        lis1();
        lis2();
        printf("%d\n",n-sum());
    }
    return 0;
}
© 2018 - fluyy - 粤ICP备17114935号