http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28415#problem/F
| 题目大意：有n个士兵排成一列，将军想从中抽出最少人数使队伍中任何士兵都能够看到左边最远处或右边最远处 |
解题思路：①此题是最长上升子序列的升级版。 ②这里先介绍一下最长上升子问题（LIS）：给定n个数从右往左选出尽量多的数，组成一个上升子序 列，相邻的不能相等 ——> 设d[i]表示以第i个数结尾的最长上升子序列，则状态转移方程为：d[i]= max{0,d[j]|j<i,a[j]<a[i]},答案是max{d[i]}; ③此题可从左往右求出d[](代码里为b[]),再从右往左求出d[](代码里为c[]),答案就是max{b[i]+c[j] | i<j} |
View Code
|
