本题我想拿它和一些题一起写：
先写一下模板：属于自己的模板
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxn=1001;
int a[maxn],num[maxn];
int main()
{
int n;
std::ios::sync_with_stdio(false);
while(cin>>n)
{
for(int i = 0; i < n; i++)
{
cin>>a[i];
num[i]=1;
}
int l=0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(a[i]>(<)a[j]&&num[j]+1>num[i])
{
num[i]=num[j]+1;
if(l<num[i])
l=num[i];
}
}
}
cout<<l<<endl;
}
return 0;
}
地下这一类是最基础的：
一、直接求最长递增（递减）子序列的长度：或去除元素的个数
1、
|
D.二等队形 | |||||
| |||||
|
Description | |||||
|
所谓二等队形就是从大到小依次排列，即对于数列a，二等队形为任意a【i】满足：a【i】>a【i+1】。 现在给出一个长度为n的数列，从中最少去除多少个数可使数列变成二等队形数列。 | |||||
|
Input | |||||
|
多组输入数据。 第一行输入n（0<n<1000）。 第二行输入长度为n的数列a(0<ai<100000)。 | |||||
|
Output | |||||
|
最少去除的元素的个数。 | |||||
|
Sample Input | |||||
|
5 6 1 4 2 3 | |||||
|
Sample Output | |||||
|
2 |
|
小乐乐大逃亡 | ||||||
| ||||||
|
Description | ||||||
|
小乐乐刚装完化妆品，突然大地摇晃，藏宝洞开始崩塌。小乐乐连忙往外跑，可原本的洞口居然出现了一条河！还好，河面上有一排高低不一的木桩，每个木桩上有一只地鼠。当踩了一个高度的木桩后，高度小于等于它的木桩和它左边的木桩都会全部崩塌。小乐乐看见地鼠十分生气，因为反应并不迅捷的她，每每玩打地鼠的游戏时，总有一种被地鼠玩弄的感觉（一个都没打到……啊哈哈哈哈哈……）。所以小乐乐想踩尽量多的地鼠，以解心头之挫败感……现在小乐乐想知道，她最多能踩扁几只地鼠？ | ||||||
|
Input | ||||||
|
第一行输入一个n（n<1000) | ||||||
|
Output | ||||||
|
输出小乐乐最多能踩扁的地鼠的个数 | ||||||
|
Sample Input | ||||||
|
7 | ||||||
|
Sample Output | ||||||
|
4 | ||||||
|
Author | ||||||
|
tju |
这两道题直接粘上面的模板就过了
二、第二类题目不但要输出数量 还要输出是哪一个，比如上两道题从左到右一次输出，
我先试一下哈
#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
const int maxn=101;
int a[maxn],fa[maxn],num[maxn];
int main()
{
int n;
std::ios::sync_with_stdio(false);
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
num[i]=1;
fa[i]=i;
}
int init=0,Max=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[i]>a[j]&&num[j]+1>num[i])
{
num[i]=num[j]+1;
if(Max<num[i])
{
Max=num[i];
init=i;
fa[i]=j;
}
}
}
}
stack<int>s;
s.push(init+1);
while(fa[init]!=init)
{
s.push(fa[init]+1);
init=fa[init];
}
cout<<s.top();
s.pop();
while(!s.empty())
{
cout<<" "<<s.top();
s.pop();
}
cout<<endl;
}
return 0;
}
运用到栈 感觉不好
题目是选美大赛：
|
选美大赛 | ||||||
| ||||||
|
Description | ||||||
|
一年一度的哈理工选美大赛开始了.来自各个院系的N个美女们都在一起排成一排，然后从左到右给他们标号(1-N),评委叫兽开始观摩,由于身高高低都不同, 叫兽想从中选出尽可能多的人使得他们的身高从左到右依次递增，你能帮助叫兽吗？ | ||||||
|
Input | ||||||
|
输入数据第一行一个数据表示美女的个数N(0<N<100) 接下来有N个数据表示1-N标号的美女的身高，身高范围都在0-180之内 当N=0时候输入结束 | ||||||
|
Output | ||||||
|
按照样例输出，首先The number is N：N是选出最多美女个数,然后后面输出N个数，代表选出美女的标号,从左到右依次输出. 题目保证答案唯一 | ||||||
|
Sample Input | ||||||
|
3 2 1 2 3 1 2 3 0 | ||||||
|
Sample Output | ||||||
|
The number is 2: 2 3 The number is 3: 1 2 3 | ||||||
|
Author | ||||||
|
万祥 |
三、
像山峰样子的队列
|
E.一等队形 | |||||
| |||||
|
Description | |||||
|
N位士兵站成一排，长官要请其中的(N-K)位出列，使得剩下的K位士兵排成一等队形。一等队形是指这样的一种队形：设K位士兵从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti，Ti>Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位士兵的身高，计算最少需要几位士兵出列，可以使得剩下的排成一等队形。
| |||||
|
Input | |||||
|
多组输入数据。 输入的第一行是一个整数N(2<=N<=100)，表示士兵的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位士兵的身高(厘米)。 | |||||
|
Output | |||||
|
输出一个数代表最少需要几位士兵出列。 | |||||
|
Sample Input | |||||
|
8 186 186 150 200 160 130 197 220 | |||||
|
Sample Output | |||||
|
4 |
代码如下：
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxn=101;
int a[maxn],b[maxn],num1[maxn],num2[maxn];
int main()
{
int n;
std::ios::sync_with_stdio(false);
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
num1[i]=1;
num2[i]=1;
}
int max1=0;
int max2=0;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
if(a[i]>a[j]&&num1[j]+1>num1[i])
num1[i]=num1[j]+1;
for(int i=n-1;i>=0;i--)
for(int j=n-1;j>i;j--)
if(a[i]>a[j]&&num2[j]+1>num2[i])
num2[i]=num2[j]+1;
int MAX=0;
for(int i=0;i<n;i++)
{
int now=num1[i]+num2[i]-1;
if(MAX<now)
MAX=now;
}
cout<<n-MAX<<endl;
}
return 0;
}
底下还有大牛的一篇文章
最长递增子序列（LIS）
文章作者：Yx.Ac 文章来源：勇幸|Thinking (http://www.ahathinking.com) 转载请注明，谢谢合作。
---
最长递增子序列又叫做最长上升子序列；子序列，正如LCS一样，元素不一定要求连续。本节讨论实现三种常见方法，主要是练手。
题：求一个一维数组arr[i]中的最长递增子序列的长度，如在序列1，-1，2，-3，4，-5，6，-7中，最长递增子序列长度为4，可以是1，2，4，6，也可以是-1，2，4，6。
方法一：DP
像LCS一样，从后向前分析，很容易想到，第i个元素之前的最长递增子序列的长度要么是1（单独成一个序列），要么就是第i-1个元素之前的最长递增子序列加1，可以有状态方程：
LIS[i] = max{1,LIS[k]+1}，其中，对于任意的k<=i-1，arr[i] > arr[k]，这样arr[i]才能在arr[k]的基础上构成一个新的递增子序列。
代码如下：在计算好LIS长度之后，output函数递归输出其中的一个最长递增子序列。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> using namespace std;
/* 最长递增子序列 LIS * 设数组长度不超过 30 * DP */
int dp[31]; /* dp[i]记录到[0,i]数组的LIS */ int lis; /* LIS 长度 */
int LIS(int * arr, int size) { for(int i = 0; i < size; ++i) { dp[i] = 1; for(int j = 0; j < i; ++j) { if(arr[i] > arr[j] && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; if(dp[i] > lis) { lis = dp[i]; } } } } return lis; }
/* 输出LIS */ void outputLIS(int * arr, int index) { bool isLIS = 0; if(index < 0 || lis == 0) { return; } if(dp[index] == lis) { --lis; isLIS = 1; }
outputLIS(arr,--index);
if(isLIS) { printf("%d ",arr[index+1]); } }
void main() { int arr[] = {1,-1,2,-3,4,-5,6,-7};
/* 输出LIS长度； sizeof 计算数组长度 */ printf("%d\n",LIS(arr,sizeof(arr)/sizeof(int)));
/* 输出LIS */ outputLIS(arr,sizeof(arr)/sizeof(int) - 1); printf("\n"); } |
这个方法也最容易想到也是最传统的解决方案，对于该方法和LIS，有以下两点说明：
1 由LIS可以衍生出来最长非递减子序列，最长递减子序列，道理是一样的。
2 对于输出序列，也是可以再申请一数组pre[i]记录子序列中array[i]的前驱，道理跟本节的实现也是一样的
方法二：排序+LCS
这个方法是在Felix’blog（见参考资料）中看到的，因为简单，他在博文中只是提了一句，不过为了练手，虽然懒，还是硬着头皮写一遍吧，正好再写一遍快排，用quicksort + LCS，这个思路还是很巧妙的，因为LIS是单调递增的性质，所以任意一个LIS一定跟排序后的序列有LCS，并且就是LIS本身。代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <iostream> using namespace std;
/* 最长递增子序列 LIS * 设数组长度不超过 30 * quicksort + LCS */
void swap(int * arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
void qsort(int * arr, int left, int right) { if(left >= right) return ; int index = left; for(int i = left+1; i <= right; ++i) { if(arr[i] < arr[left]) { swap(arr,++index,i); } } swap(arr,index,left); qsort(arr,left,index-1); qsort(arr,index+1,right); }
int dp[31][31];
int LCS(int * arr, int * arrcopy, int len) { for(int i = 1; i <= len; ++i) { for(int j = 1; j <= len; ++j) { if(arr[i-1] == arrcopy[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; }else if(dp[i-1][j] > dp[i][j-1]) { dp[i][j] = dp[i-1][j]; }else { dp[i][j] = dp[i][j-1]; } } } return dp[len][len]; }
void main() { int arr[] = {1,-1,2,-3,4,-5,6,-7}; int arrcopy [sizeof(arr)/sizeof(int)];
memcpy(arrcopy,arr,sizeof(arr)); qsort(arrcopy,0,sizeof(arr)/sizeof(int)-1);
/* 计算LCS，即LIS长度 */ int len = sizeof(arr)/sizeof(int); printf("%d\n",LCS(arr,arrcopy,len)); } |
方法三：DP+二分查找
《编程之美》对于这个方法有提到，不过它的讲解我看得比较难受，好长时间才明白，涉及到的数组也比较多，除了源数据数组，有LIS[i]和MaxV[LIS[i]]，后来看了大牛Felix的讲解，我才忽然发现编程之美中的这个数组MaxV[LIS[i]]在记录信息上其实是饶了弯的，因为我们在寻找某一长度子序列所对应的最大元素最小值时，完全没必要通过LIS[i]去定位，即没必要与数据arr[i]挂钩，直接将MaxV[i]的下标作为LIS的长度，来记录最小值就可以了（表达能力太次，囧。。。），一句话，就是不需要LIS[i]这个数组了，只用MaxV[i]即可达到效果，而且原理容易理解，代码表达也比较直观、简单。
下面说说原理：
目的：我们期望在前i个元素中的所有长度为len的递增子序列中找到这样一个序列，它的最大元素比arr[i+1]小，而且长度要尽量的长，如此，我们只需记录len长度的递增子序列中最大元素的最小值就能使得将来的递增子序列尽量地长。
方法：维护一个数组MaxV[i]，记录长度为i的递增子序列中最大元素的最小值，并对于数组中的每个元素考察其是哪个子序列的最大元素，二分更新MaxV数组，最终i的值便是最长递增子序列的长度。这个方法真是太巧妙了，妙不可言。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> using namespace std;
/* 最长递增子序列 LIS * 设数组长度不超过 30 * DP + BinarySearch */
int MaxV[30]; /* 存储长度i+1（len）的子序列最大元素的最小值 */ int len; /* 存储子序列的最大长度 即MaxV当前的下标*/
/* 返回MaxV[i]中刚刚大于x的那个元素的下标 */ int BinSearch(int * MaxV, int size, int x) { int left = 0, right = size-1; while(left <= right) { int mid = (left + right) / 2; if(MaxV[mid] <= x) { left = mid + 1; }else { right = mid - 1; } } return left; }
int LIS(int * arr, int size) { MaxV[0] = arr[0]; /* 初始化 */ len = 1; for(int i = 1; i < size; ++i) /* 寻找arr[i]属于哪个长度LIS的最大元素 */ { if(arr[i] > MaxV[len-1]) /* 大于最大的自然无需查找，否则二分查其位置 */ { MaxV[len++] = arr[i]; }else { int pos = BinSearch(MaxV,len,arr[i]); MaxV[pos] = arr[i]; } } return len; }
void main() { int arr[] = {1,-1,2,-3,4,-5,6,-7};
/* 计算LIS长度 */ printf("%d\n",LIS(arr,sizeof(arr)/sizeof(int))); } |
这个方法的实现巧妙而直观，让人有种“啊，原来还可以这样”的感慨，感谢Felix。
本文相关代码可以到这里下载。
（全文完）
参考资料：
《编程之美》 2.16
Felix’s Blog：最长递增子序列 O(NlogN)算法
勘误：
第三种方法细节有错误，见下面评论，感谢@冰上游鱼
分类:算法 数据结构标签:LIS, 二分查找, 最大下降子序列, 最长上升子序列, 最长递增子序列, 最长非递减子序列, 编程之美