算法提高课DP最长上升子序列模型总结
详细题解
1.AcWing895.最长上升子序列题解
2.AcWing 1017.怪盗基德的滑翔翼题解
3.AcWing 1014. 登山题解
4.AcWing 482. 合唱队形题解
5.AcWing 1012. 友好城市题解
6.AcWing 1016. 最大上升子序列题解
模块总结
总结(在本文,无超链接)暂未写
AcWing895. 最长上升子序列
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤1000,
−109≤数列中的数≤109
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
思路
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int f[N];
int w[N];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,f[i]);
printf("%d",res);
return 0;
}
AcWing 1017. 怪盗基德的滑翔翼
怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。
而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。
不得已,怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。
初始时,怪盗基德可以在任何一幢建筑的顶端。
他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。
因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。
他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。
请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?
输入格式
输入数据第一行是一个整数K,代表有K组测试数据。
每组测试数据包含两行:第一行是一个整数N,代表有N幢建筑。第二行包含N个不同的整数,每一个对应一幢建筑的高度h,按照建筑的排列顺序给出。
输出格式
对于每一组测试数据,输出一行,包含一个整数,代表怪盗基德最多可以经过的建筑数量。
数据范围
1≤K≤100,
1≤N≤100,
0<h<10000
输入样例:
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10
输出样例:
6
6
9
思路
其实就是双向(从左到右,从右到左)各求一次最长上升子序列
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int q,n;
int f[N];
int w[N];
int main(){
scanf("%d",&q);
while(q--){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
//正向求LIS问题
int res=0;
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
//反向求LIS问题
for(int i=n-1;i>=0;i--){
f[i]=1;
for(int j=n-1;j>i;j--)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
printf("%d\n",res);
}
return 0;
}
AcWing 1014. 登山
AcWing 482. 合唱队形
五一到了,ACM队组织大家去登山观光,队员们发现山上一共有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。
队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?
输入格式
第一行包含整数N,表示景点数量。
第二行包含N个整数,表示每个景点的海拔。
输出格式
输出一个整数,表示最多能浏览的景点数。
数据范围
2≤N≤1000
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
思路
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int w[N],f[N],g[N];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
//正向求LIS问题
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+1);
}
//反向求LIS问题
for(int i=n-1;i>=0;i--){
g[i]=1;
for(int j=n-1;j>i;j--)
if(w[i]>w[j])
g[i]=max(g[i],g[j]+1);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,f[i]+g[i]-1); //因为顶点算了两次,所以res要-1
printf("%d",res);
return 0;
}
合唱队形思路跟登山一样,就是最后结果要的是n-res
需要的UU可以点目录中对应题目的蓝字,看详细代码哦~
AcWing 1012. 友好城市
Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。
编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。
输入格式
第1行,一个整数N,表示城市数。
第2行到第n+1行,每行两个整数,中间用1个空格隔开,分别表示南岸和北岸的一对友好城市的坐标。
输出格式
仅一行,输出一个整数,表示政府所能批准的最多申请数。
数据范围
1≤N≤5000,
0≤xi≤10000
输入样例:
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例:
4
思路
显然,假使路线都不冲突的话,那么对其中某一岸边城市从小到大排序后,该岸城市所对应的对岸城市也应该是从小到大排序,因此如果有冲突的话,我们仅需对其中一岸城市进行排序,再对另外一岸找到最长上升子序列即为最大不冲突路线数
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
pair<int,int> q[N];
int f[N];
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&q[i].first,&q[i].second);
sort(q,q+n); //默认按照first排序
//对first排序,然后对second取最长上升子序列
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++)
if(q[i].second>q[j].second)
f[i]=max(f[i],f[j]+1);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,f[i]);
printf("%d",res);
return 0;
}
AcWing 1016. 最大上升子序列和
数据范围
1≤N≤1000
输入样例:
7
1 7 3 5 9 4 8
输出样例:
18
思路
就是最长的集合(f[N])初始化为1(f[i]=1),最大的集合(f[N])初始化为f[i]=w[i]
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N],w[N];
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
for(int i=0;i<n;i++){
f[i]=w[i]; //跟最长子序列不一样的就是将集合f[N]初始化为当前位置的权重
for(int j=0;j<i;j++)
if(w[i]>w[j])
f[i]=max(f[i],f[j]+w[i]);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,f[i]);
printf("%d",res);
return 0;
}
写的很好呀