网站开发员岗位职责,电影html网页模板设计素材,建设网站的那个公司好,凡客诚品特色文章目录 最长上升子序列回顾题目描述问题分析程序代码复杂度分析 怪盗基德的滑翔翼题目描述输入格式输出格式 问题分析程序代码复杂度分析 登山题目描述输入格式输出格式 问题分析程序代码复杂度分析 合唱队形题目描述输入格式输出格式 问题分析程序代码复杂度分析 友好城市题… 文章目录 最长上升子序列回顾题目描述问题分析程序代码复杂度分析 怪盗基德的滑翔翼题目描述输入格式输出格式 问题分析程序代码复杂度分析 登山题目描述输入格式输出格式 问题分析程序代码复杂度分析 合唱队形题目描述输入格式输出格式 问题分析程序代码复杂度分析 友好城市题目描述输入格式输出格式 问题分析程序代码复杂度分析 最大上升子序列和题目描述输入格式输出格式 问题分析程序代码复杂度分析 最长上升子序列回顾
题目描述
给定一个长度为 N 的数列求数值严格单调递增的子序列的长度最长是多少。
问题分析
状态表示dp[i]表示所有以a[i]结尾的严格单调上升子序列的最大长度。
状态计算dp[i] max(dp[i], dp[k] 1)其中需要满足a[k] a[i]
程序代码
#include iostream
using namespace std;const int N 1010;
int a[N], dp[N];int main()
{int n;cin n;for(int i 1; i n; i) {cin a[i];}int res 0;for(int i 1; i n; i) {dp[i] 1;for(int j 1; j i; j) {if(a[j] a[i]) {dp[i] max(dp[i], dp[j] 1);}}res max(res, dp[i]);}cout res endl;return 0;
}复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
怪盗基德的滑翔翼
题目描述
怪盗基德是一个充满传奇色彩的怪盗专门以珠宝为目标的超级盗窃犯。
而他最为突出的地方就是他每次都能逃脱中村警部的重重围堵而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天怪盗基德像往常一样偷走了一颗珍贵的钻石不料却被柯南小朋友识破了伪装而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。
不得已怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线每幢建筑的高度各不相同。
初始时怪盗基德可以在任何一幢建筑的顶端。
他可以选择一个方向逃跑但是不能中途改变方向因为中森警部会在后面追击。
因为滑翔翼动力装置受损他只能往下滑行即只能从较高的建筑滑翔到较低的建筑。
他希望尽可能多地经过不同建筑的顶部这样可以减缓下降时的冲击力减少受伤的可能性。
请问他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)
输入格式
输入数据第一行是一个整数K代表有K组测试数据。
每组测试数据包含两行第一行是一个整数N代表有N幢建筑。第二行包含N个不同的整数每一个对应一幢建筑的高度h按照建筑的排列顺序给出。
输出格式
对于每一组测试数据输出一行包含一个整数代表怪盗基德最多可以经过的建筑数量。
问题分析
这道题可以转化为两个方向的最长上升子序列问题。【裸题相信你可以直接 A 了】
程序代码
#include iostream
using namespace std;const int N 110;
int a[N], dp[N];int main()
{int t;cin t;while( t-- ) {int n;cin n;int res 0;for(int i 1; i n; i) {cin a[i];}// 正向求解LISfor(int i 1; i n; i) {dp[i] 1;for(int j 1; j i; j) {if(a[j] a[i]) dp[i] max(dp[i], dp[j] 1);}res max(dp[i], res);}// 反向求解LISfor(int i n; i 1; i--) {dp[i] 1;for(int j n; j i; j--) {if(a[j] a[i]) dp[i] max(dp[i], dp[j] 1);}res max(dp[i], res);}cout res endl;}return 0;
}复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
登山
题目描述
五一到了ACM队组织大家去登山观光队员们发现山上一共有N个景点并且决定按照顺序来浏览这些景点即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯就是不连续浏览海拔相同的两个景点并且一旦开始下山就不再向上走了。
队员们希望在满足上面条件的同时尽可能多的浏览景点你能帮他们找出最多可能浏览的景点数么
输入格式
第一行包含整数N表示景点数量。
第二行包含N个整数表示每个景点的海拔。
输出格式
输出一个整数表示最多能浏览的景点数。
问题分析
对于这道题本质上是找一个分割点k求以 k 结尾的最长上升子序列长度f[k]和以 k 开头的最长下降子序列g[k]然后求f[k] g[k]的最大值。
程序代码
#include iostream
using namespace std;const int N 1010;
int a[N], f[N], g[N];int main()
{int n;cin n;for(int i 1; i n; i) {cin a[i];}// 正向求解LISfor(int i 1; i n; i) {f[i] 1;for(int j 1; j i; j) {if(a[j] a[i]) f[i] max(f[i], f[j] 1);}}// 反向求解LIS就是以i开头的最长下降子序列for(int i n; i 1; i--) {g[i] 1;for(int j n; j i; j--) {if(a[j] a[i]) g[i] max(g[i], g[j] 1);}}int res 0;for(int i 1; i n; i) {res max(res, f[i] g[i] - 1);}cout res endl;return 0;
}复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
合唱队形
题目描述
N 位同学站成一排音乐老师要请其中的 (N−K) 位同学出列使得剩下的 K 位同学排成合唱队形。
合唱队形是指这样的一种队形设 K 位同学从左到右依次编号为 12…K他们的身高分别为 T 1 T 2 … T K T_1T_2…T_K T1T2…TK 则他们的身高满足 T 1 . . . T i T i 1 . . . T K ( 1 ≤ i ≤ K ) T_1 ... T_i T_{i1} ... T_K(1 \leq i \leq K) T1...TiTi1...TK(1≤i≤K)。
你的任务是已知所有 N 位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数 N表示同学的总数。
第二行有 N 个整数用空格分隔第 i 个整数 T i T_i Ti 是第 i 位同学的身高(厘米)。
输出格式
输出包括一行这一行只包含一个整数就是最少需要几位同学出列。
问题分析
这道题其实就是用总数 n 减去上面那道登山问题求出来的最多能浏览的景点数。
程序代码
#include iostream
using namespace std;const int N 1010;
int a[N], f[N], g[N];int main()
{int n;cin n;for(int i 1; i n; i) {cin a[i];}// 正向求解LISfor(int i 1; i n; i) {f[i] 1;for(int j 1; j i; j) {if(a[j] a[i]) f[i] max(f[i], f[j] 1);}}// 反向求解LIS就是以i开头的最长下降子序列for(int i n; i 1; i--) {g[i] 1;for(int j n; j i; j--) {if(a[j] a[i]) g[i] max(g[i], g[j] 1);}}int res 0;for(int i 1; i n; i) {res max(res, f[i] g[i] - 1);}cout n - res endl;return 0;
}复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
友好城市
题目描述
Palmia国有一条横贯东西的大河河有笔直的南北两岸岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市但是由于河上雾太大政府决定避免任意两条航道交叉以避免事故。
编程帮助政府做出一些批准和拒绝申请的决定使得在保证任意两条航线不相交的情况下被批准的申请尽量多。
输入格式
第1行一个整数N表示城市数。
第2行到第n1行每行两个整数中间用1个空格隔开分别表示南岸和北岸的一对友好城市的坐标。
输出格式
仅一行输出一个整数表示政府所能批准的最多申请数。
问题分析
前提条件每个城市有且仅有一个友好城市在对岸而且不同城市的友好城市不相同
这道题要求在满足如下约束的情况下建立尽可能多的桥
每个城市上只能建立一座桥只有友好城市之间能建立一座桥所有的桥之间不能相交 以南岸的城市为基准我们可以发现对于任意一种建桥的可行方案北岸的城市位置都是严格单调递增的。
换言之我们建立一个二元组a, ba表示南岸的城市位置b表示北岸的城市位置。若两个桥之间不相交则必有当a1 a2时b1 b2。
因此我们可以将所有的友好城市建立成一组二元组a, b将二元组按照南岸的位置a升序排序然后找关于b的最长上升子序列。
程序代码
#include iostream
#include algorithm
using namespace std;typedef pairint, int PII;const int N 5050;int n;
PII a[N];
int dp[N];int main()
{cin n;for(int i 0; i n; i) {cin a[i].first a[i].second;}sort(a, a n);int res 0;for(int i 0; i n; i) {dp[i] 1;for(int j 0; j i; j) {if(a[i].second a[j].second) {dp[i] max(dp[i], dp[j] 1);}}res max(res, dp[i]);}cout res endl;return 0;
}复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
最大上升子序列和
题目描述
一个数的序列 b i b_i bi当 b 1 b 2 … b S b_1b_2…b_S b1b2…bS 的时候我们称这个序列是上升的。
对于给定的一个序列 ( a 1 , a 2 , … , a N ) (a_1,a_2,…,a_N) (a1,a2,…,aN)我们可以得到一些上升的子序列 ( a i 1 , a i 2 , … , a i K ) (a_{i1},a_{i2},…,a_{iK}) (ai1,ai2,…,aiK)这里 1 ≤ i 1 i 2 … i K ≤ N 1≤i_1i_2…i_K≤N 1≤i1i2…iK≤N。
比如对于序列 ( 1 , 7 , 3 , 5 , 9 , 4 , 8 ) (1,7,3,5,9,4,8) (1,7,3,5,9,4,8)有它的一些上升子序列如 ( 1 , 7 ) , ( 3 , 4 , 8 ) (1,7),(3,4,8) (1,7),(3,4,8) 等等。
这些子序列中和最大为18为子序列 ( 1 , 3 , 5 , 9 ) (1,3,5,9) (1,3,5,9) 的和。
你的任务就是对于给定的序列求出最大上升子序列和。
注意最长的上升子序列的和不一定是最大的比如序列 ( 100 , 1 , 2 , 3 ) (100,1,2,3) (100,1,2,3) 的最大上升子序列和为100而最长上升子序列为 ( 1 , 2 , 3 ) (1,2,3) (1,2,3)。
输入格式
输入的第一行是序列的长度N。
第二行给出序列中的N个整数这些整数的取值范围都在0到10000(可能重复)。
输出格式
输出一个整数表示最大上升子序列和。
问题分析
这道题对最长上升子序列问题的状态定义和状态计算进行一定的微调即可。
状态表示dp[i]表示所有以a[i]结尾的严格单调上升子序列的最大和。
状态计算dp[i] max(dp[i], dp[k] a[i])其中需要满足a[k] a[i]
程序代码
#include iostream
#include algorithm
using namespace std;const int N 1010;
int a[N], dp[N];
int n;int main()
{cin n;for(int i 1; i n; i) {cin a[i];}int res 0;for(int i 1; i n; i) {dp[i] a[i];for(int j 1; j i; j) {if(a[i] a[j]) {dp[i] max(dp[i], dp[j] a[i]);}}res max(res, dp[i]);}cout res endl;return 0;
}复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
