线性动规
LIS类型DP
【例题1】：最长不下降序列1078
Description:
设有整数序列b1,b2,b3,……,bm, 若存在i1< i2 第一行为一个数n，表示有n个数，第二行为n个整数序列； Output: 第一行为最大长度，第二行为满足长度的序列 Sample Input 14 13 7 9 16 38 24 37 18 4 19 21 22 63 15 Sample Output 8 7 9 16 18 19 21 22 63 【试题分析】 1、阶段和状态： f[i]：表示以a[i]为最后一个数字的最长不下降序列的最大长度； 阶段i表示前i个数，由于每个阶段只有一个状态，所以用一维数组表示； 2、状态转移方程： 初始化：f[i]=1; f[i]=max{f[j]+1,j 初始化： i a[i] f[i] 1 13 1 2 7 1 0 3 9 1 0 4 5 6 7 8 9 4 1 0 10 11 12 13 14 19 21 22 63 15 1 0 1 0 1 0 1 0 1 0 16 38 24 37 18 1 0 1 0 1 0 1 0 1 0 pre[i] 0 计算过程： i a[i] f[i] 1 13 1 2 7 1 2 3 9 2 2 4 5 6 7 8 9 4 1 9 10 11 12 13 14 19 21 22 63 15 5 8 6 7 8 3 3 16 38 24 37 18 3 3 4 4 4 4 5 6 4 4 pre[i] 1 10 11 12 3、核心子程序： 说明 数组p[i]记录第i个数前一个结点下标。 void out(int pre[],int a[],int n) //递归输出序列 { if (pre[n]==n){cout<>n; for(i=1;i<=n;i++) {cin>>a[i];f[i]=1;pre[i]=i;}//初始化 for(i=2;i<=n;i++) for(j=1;j 【例题2】渡轮问题1373 Description 有一个国家被一条河划分为南北两部分，在南岸和北岸总共有N对城镇，每一城镇在对岸都有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉(如果两条航线交叉，将有很大机会撞船)。 你的任务是写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使得没有出现交叉的航线最多。 Input 第一行一个整数N(1 <= N <= 1000)，表示分布在河两岸的城镇对数。 接下来的N行每行有两个由空格分隔的正数C，D ( C、D<=10^9 )，描述每一对友好城镇沿着河岸与西边境线的距离，C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边，任何两个城镇的位置都是不同的。 Output 在安全条件下能够开通的最大航线数目。 Sample Input 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 Sample Output 4 【试题分析】： 1、阶段和状态：题目粗略一看，不能够用动态规划求解，因为具有后效性,但是仔细分析如果先按照a[i]从小到大排序后,解除了后效性,问题变成了对于b[i]求最长上升子序列问题 f[i]:表示以b[i]为最后一个数字的最长不下降序列的最大长度 注意：好多题目都要通过排序解除后效性！！ 2、状态转移方程： 初始化：f[i]=1;(1<=i<=n) f[i]=max{f[j]+1,j 【例题3】合唱队形1001 Description N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得Ti 你的任务是，已知所有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 数据规模 对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。 【试题分析】 动态规划。最基本的想法是：枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基准）。时间复杂度为O(n^3)，算法实现起来也很简单。 接着对这个算法进行分析，我们不难发现，假如还是基于枚举一个同学的话，设Incsq[i]表示了1 - i的最长上升序列，Decsq[i]表示了i - n的最长下降序列，那么， Current[i] = Incsq[i] + Decsq[i] - 1（两个数组中i被重复计算了） 那么，我们只需要先求好最长上升和下降序列，然后枚举中间最高的同学就可以了。 【算法优化】 求最长上升序列的经典状态转移方程为： opt[i] = max{opt[j]+1, 其中i 我们对状态转移方程稍微做一些修改： opt[i] = max{opt[i+1], min{j, rec[j]>=list[i]}} rec[j] = list[i] 很明显可以看出，在opt[i]的寻找j的过程当中，查询序列是单调的，于是可以用二分法，就十分巧妙地在logn的时间内找到指定的j，而问题的总体复杂度为O(nlogn)。这样，这个问题的算法效率就得到了大幅度的提升，即便n是106，也可以轻松应对。 【C参考代码】 #include ifstream fin(\ ofstream fout(\ const int maxn = 100; int n, a[maxn]; int incsq[maxn], decsq[maxn]; void init() { fin >> n; for (int i = 0; i < n; i ++) fin >> a[i]; } void LIncSeq() { int i, low, high, mid, ans = 0; int sol[maxn]; for (i = 0; i < n; i ++) { low = 1; high = ans; while (low <= high) { mid = (low + high) >> 1; if (sol[mid] < a[i]) low = mid + 1; else high = mid - 1; } if (low > ans) ans ++; sol[low] = a[i]; incsq[i] = ans; } } void LDecSeq() { int i, low, high, mid, ans = 0; int sol[maxn]; for (i = 0; i < n; i ++) { low = 1; high = ans; while (low <= high) { mid = (low + high) >> 1; if (sol[mid] > a[i]) low = mid + 1; else high = mid - 1; } if (low > ans) ans ++; sol[low] = a[i]; decsq[i] = ans; } } void work() { int i, max = 0; LIncSeq(); LDecSeq(); for (i = 0; i < n; i ++) if (incsq[i] + decsq[i] - 1 > max) max = incsq[i] + decsq[i] - 1; fout << n - max << endl; } int main() { init();