动态规划-LIS

心已赠人 2021-12-23 11:09 213阅读 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 条评论，213人围观）

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

相关阅读

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

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

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

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

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

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

相关动态添加删除li

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

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

相关动态规划

首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 263 阅读

相关动态规划

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

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

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

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

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

相关动态规划

1.题目：最长递增子序列（Longest Increasing Subsequence）问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 224 阅读

相关动态规划-LIS

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

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

相关动态规划

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

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

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

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

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