动态规划-LIS

心已赠人 2021-12-23 11:09 248阅读 0赞

[https://vjudge.net/contest/297216?tdsourcetag=s\_pctim\_aiomsg\#problem/E][https_vjudge.net_contest_297216_tdsourcetag_s_pctim_aiomsg_problem_E]

#include<bits/stdc++.h>
    using namespace std; struct note { int x,y,id; } m[1005]; int f[1005]; int c[1005]; set<int> s; bool cmp(note a,note b) { return a.x<b.x; } int main() { int cnt=0; int x,y; while(cin>>x>>y) { m[++cnt].x=x; m[cnt].y=y; m[cnt].id=cnt; } sort(m+1,m+1+cnt,cmp); for(int i=1; i<=cnt; i++) for(int j=1; j<i; j++) { if(m[i].y<m[j].y&&m[i].x>m[j].x&&f[i]<f[j]+1) { f[i]=f[j]+1; c[i]=j; } } int flag=1; int maxx=f[1]; for(int i=2;i<=cnt;i++) { if(f[i]>maxx) { maxx=f[i]; flag=i; } } while(flag!=0) { s.insert(flag); flag=c[flag]; } printf("%d\n",s.size()); for(auto i:s) printf("%d\n",m[i].id); // s.insert(m[flag].id); // while(c[flag]!=0) // { // s.insert(m[c[flag]].id); // flag=c[flag]; // } // printf("%d\n",s.size()); // for(auto i:s) // printf("%d\n",i);
     }

转载于:https://www.cnblogs.com/dongdong25800/p/10782025.html

[https_vjudge.net_contest_297216_tdsourcetag_s_pctim_aiomsg_problem_E]: https://vjudge.net/contest/297216?tdsourcetag=s_pctim_aiomsg#problem/E

发表评论取消回复

表情：

评论列表（有 0 条评论，248人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode】动态规划问题：LCS 与 LIS 问题

LIS 问题 [300. 最长递增子序列][300.] 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不

Myth丶恋晨/ 2022年10月29日 09:13/ 0 赞/ 142 阅读

相关动态规划

-------------------- 动态规划的设计思想动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 239 阅读

相关 429-动态规划算法-最长非降子序列LIS

LIS问题：求序列的最长非降（升序）子序列的长度 5 3 4 1 8 7 9 我们看上面这个序列。显然，5和3不能构成非降子序列。3和4就可以构成非降子序列。以

谁借莪１个温暖的怀抱￠/ 2022年09月05日 04:29/ 0 赞/ 129 阅读

相关动态添加删除li

这个功能的需求是这样的，接收人处显示多个用户名（是结果），在输入框输入完成后，回车键或者失去焦点，就去查询，查询结果出来后，通过点击加号再添到接收人处。

痛定思痛。/ 2022年08月18日 13:15/ 0 赞/ 211 阅读

相关动态规划

基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：与

ゞ浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 426 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 299 阅读

相关动态生成li 根据后台返回个数动态生成li

//根据后台返回端口个数动态生成 for (let i = 0; i < 8; i++) { var temp=` <li><p>P`+i+`</p

桃扇骨/ 2022年05月16日 05:56/ 0 赞/ 219 阅读

相关动态规划-LIS

[https://vjudge.net/contest/297216?tdsourcetag=s\_pctim\_aiomsg\problem/E][https_vjud

心已赠人/ 2021年12月23日 11:09/ 0 赞/ 249 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 472 阅读

相关动态规划-最长上升子序列LIS

文章目录问题描述一.简单推论（非0 n情况） 1.问题分析 2.状态转移方程 3.参考代码 4

￡神魔★判官ぃ/ 2021年09月07日 06:03/ 0 赞/ 425 阅读