苏晋建设集团网站,如何自己写一个网站,建设厅特种作业,wordpress pdf 打印文章目录
怪盗基德的滑翔翼登山合唱队形友好城市最大上升子序列和拦截导弹导弹防御系统最长公共上升子序列 一、怪盗基德的滑翔翼OJ链接 本题思路:本题是上升子序列模型中比较简单的模型#xff0c;分别是从前往后和从后往前走一遍LIS即可。
#include bits/stdc.hco… 文章目录
怪盗基德的滑翔翼登山合唱队形友好城市最大上升子序列和拦截导弹导弹防御系统最长公共上升子序列 一、怪盗基德的滑翔翼OJ链接 本题思路:本题是上升子序列模型中比较简单的模型分别是从前往后和从后往前走一遍LIS即可。
#include bits/stdc.hconstexpr int N110;int n;
int h[N];
int f[N];int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T;std::cinT;while(T--){std::cinn;for(int i1;in;i) std::cinh[i];int res0;//正向求解LIS问题for(int i1;in;i){f[i]1;for(int j1;ji;j)if(h[j]h[i]) f[i]std::max(f[i],f[j]1);resstd::max(f[i],res);}memset(f,0,sizeof f);//这里需要将此时的f数组进行清零处理//反向求解LIS问题for(int in;i1;i--){f[i]1;for(int jn;ji;j--)if(h[j]h[i]) f[i]std::max(f[i],f[j]1);resstd::max(f[i],res);}std::coutresstd::endl;}return 0;
}
二、登山OJ链接 本题思路:状态表示f[i]表示以第 i个位置作为当前子序列的右端点的值g[i]表示以第 i 个位置作为当前子序列的左端点的值。状态属性:f[i]求最长上升子序列的最多景点个数,g[i]求最长下降子序列的最多景点个数。状态计算f[i]max(f[i],f[j]1)(1≤ji≤n)g[i]max(g[i],g[j]1)(1≤ij≤n) 求新数组最长上升子序列就是求原数组最长下降子序列答案表示:根据每一个点来划分ansmax(包含 i的最长上升子序列 包含 i的最长下降子序列)所以 ansmax(f[i]g[i]−1)。
#include bits/stdc.hconstexpr int N1010;int n;
int h[N];
int f[N],g[N];//f用来表示上升子序列 g表示下降子序列int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cinn;for(int i1;in;i) std::cinh[i];for(int i1;in;i){//求出上升子序列f[i]1;for(int j1;ji;j)if(h[j]h[i])f[i]std::max(f[i],f[j]1);}for(int in;i1;i--){//求出下降子序列g[i]1;for(int jn;ji;j--)if(h[j]h[i])g[i]std::max(g[i],g[j]1);}int res0;for(int i1;in;i)resstd::max(res,f[i]g[i]-1);std::coutresstd::endl;return 0;
}
三、合唱队形OJ链接 本题思路:本题与上面一题差不多。
#include bits/stdc.hconstexpr int N1010;int n;
int h[N];
int f[N],g[N];int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cinn;for(int i1;in;i) std::cinh[i];for(int i1;in;i){f[i]1;for(int j1;ji;j)if(h[j]h[i])f[i]std::max(f[i],f[j]1);}for(int in;i1;i--){g[i]1;for(int jn;ji;j--)if(h[j]h[i])g[i]std::max(g[i],g[j]1);}int res0;for(int i1;in;i) resstd::max(res,f[i]g[i]-1);std::coutn-resstd::endl;return 0;
}
四、友好城市OJ链接 本题思路:这里的我们可以先想想交叉和不交叉的情况下分别画出来的图是什么样子的。我们可以发现在两座桥不交叉的情况下有a1a2,b1b2在两座桥相交的情况下有a1a2,b2b1所以我们可以发现两桥是否交叉是可以用北岸城市编号的大小关系给反应出来的。所以我们的思路就可以转化为以南岸的城市编号为基准把所有的城市对从小到大排序从而得到关于北岸城市的一个数组。因为当bibj时能成功建一座桥所以问题就转化成了求取这个数组的最长上升子序列。到此我们对北方城市的数组做一次 LIS就可以得到答案了。
#include bits/stdc.h#define x first
#define y secondtypedef std::pairint, int PII;
constexpr int N5010;int n;
int f[N];
PII line[N];int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cinn;for(int i1;in;i)std::cinline[i].xline[i].y;std::sort(line1,linen1);int res0;for(int i1;in;i){for(int j0;ji;j)if(line[j].yline[i].y)f[i]std::max(f[i],f[j]1);resstd::max(res,f[i]);}std::coutresstd::endl;return 0;
} 五、最大上升子序列和OJ链接 六、拦截导弹OJ链接 七、导弹防御系统OJ链接 八、最长公共上升子序列OJ链接