这倆道题目都是求最长递增子序列，只不过各自都有点点区别
hdu 1025
题意：
• 有两行点, 每行n个. 第一行点和第二行点是一一对应的, 有线连接, 如下图所示 • 选择尽量多的线 , 两两不交叉 分析： • 设与第 1行第i个点对应的是第2行第f[i]个点 • 假设 i<j, 两条线 (i, f[i]) 和 (j, f[j]) 的充要条件是 f[i]<f[j], 因此问题变成了 求f的最长递增子序列了 hdu1025 #include<iostream>#include<algorithm>#define MAXN 500010using 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} 注意边界情况的处理 pku1836 #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;}转载于:https://www.cnblogs.com/nanke/archive/2011/08/21/2147900.html
