学步园

这倆道题目都是求最长递增子序列，只不过各自都有点点区别

hdu 1025

题意：

•有两行点, 每行n个. 第一行点和第二行点是一一对应的, 有线连接, 如下图所示

•选择尽量多的线, 两两不交叉

分析：

•

设与第

1行第i个点对应的是第2行第f[i]个点

•假设i<j, 两条线(i, f[i])和(j, f[j])的充要条件是f[i]<f[j],

因此问题变成了 求f的最长递增子序列了

#include<iostream>
#include<algorithm>
#define MAXN 500010
using namespace std;
int a[MAXN],dp[MAXN];
int main()
{
int n;
int c,b,cas=0;
while(scanf("%d",&n)==1)
    {
for(int i=0;i<n;i++)
        {
             scanf("%d %d",&c,&b);
             a[c]=b;
        }
        memset(dp,0,sizeof(dp));
int len=0;
for(int i=1;i<=n;i++)
        {
int num=a[i];
int left=1,right=len,mid;
while(left<=right)
            {
                mid=(left+right)/2;
if(dp[mid]<num)
                    left=mid+1;
else right=mid-1;
            }
            dp[left]=num;
if(left>len) len++;
        }
if(len>1)
            printf("Case %d:\nMy king, at most %d roads can be built.\n\n",++cas,len);
else printf("Case %d:\nMy king, at most %d road can be built.\n\n",++cas,len);
    }
return 0;
}

 

pku 1836

题意：  给定n个人高度，将n个人中的其中一些人出队，使得任何一个人 都能够看到左边第一个人或右边第一个人。(高度要大于才能望过去) 。求出队的最少人数

分析：两遍LIS ，一遍是从左到右，求出最长递增子序列，一遍是从右向左，求出最长递增子序列，然后穷举所有的情况，求出队伍最长的

ans = n - max{opt[i] + opt[j] | 0 < i < j < n}

注意边界情况的处理

#include<iostream>
#define MAXN 1010 
using namespace std;
float a[MAXN];
int    dp1[MAXN],dp2[MAXN];
int main()
{
int n;
while(scanf("%d",&n)==1)
    {
for(int i=0;i<n;i++)
            scanf("%f",&a[i]);
        dp1[0]=1;
for(int i=1;i<n;i++)
        {            
            dp1[i]=1;
for(int j=i-1;j>=0;j--)
            {
if(a[i]>a[j]&&dp1[i]<dp1[j]+1)
                    dp1[i]=dp1[j]+1;
            }
        }
        dp2[n-1]=1;
for(int i=n-2;i>=0;i--)
        {
            dp2[i]=1;
for(int j=i+1;j<n;j++)
            {

if(a[i]>a[j]&&dp2[i]<dp2[j]+1)
                    dp2[i]=dp2[j]+1;
            }
        }
int ans=0;
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(dp1[i]+dp2[j]>ans)
                ans=dp1[i]+dp2[j];
        printf("%d\n",n-ans);
    }
return 0;
}