// [解题方法]
// 对大象增加编号属性i,以免排序后丢失
// 对大象数组倒过来sort一下(W大的在前;若W一样,S小的在前)
// 对sort好的数组倒过来dp最长子序列,记录前驱
// 输出路径(由于是倒过来dp,所以输出路径不用栈,不断输出前驱即可)
// 复杂度O(n^2)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define M 1005
struct point {
int x, y, i;
}p[M];
bool cmp (point a, point b)
{
if (a.x == b.x) return a.y < b.y;
return a.x > b.x;
}
int nxt[M], dp[M];
int main()
{
int n = 0, i, j, maxs, v = -1;
while (cin >> p[n].x >> p[n].y) {
p[n].i = n+1;
++n;
}
sort (p, p+n, cmp);
maxs = 0;
for (i = 0; i < n; i++) {
dp[i] = 1;
nxt[i] = -1;
}
for (i = 0; i < n; i++)
{
for (j = i+1; j < n; j++)
{
if (p[j].x < p[i].x && p[j].y > p[i].y && dp[j] < dp[i]+1)
{
dp[j] = dp[i] + 1;
nxt[j] = i;
if (dp[j] > maxs) {
maxs = dp[j];
v = j;
}
}
}
}
cout << maxs << endl;
while (v >= 0)
{
cout << p[v].i << endl;
v = nxt[v];
}
return 0;
}
分享到:
相关推荐
僵尸网络(Botnet)是网络安全领域的一大威胁,其规模估算一直以来都是一个充满争议的话题。"我的僵尸网络比你的大(也许更好):为什么规模估计如此困难"这篇论文由Moheeb Abu Rajab、Jay Zarfoss、Fabian Monrose...
这个“bigger_java_bigger_android_”主题主要关注如何使用Java语言在Android平台上构建一个放大镜功能。下面将详细介绍这个功能的实现原理、关键代码以及可能遇到的问题。 首先,放大镜功能的核心思想是利用...
猫扑出品的APP,Bigger秀(破解版),免登录安装后直接可使用所有的效果,红爆你的朋友圈。
"和"The bigger one."。 这些句子和表达是英语初学者的基础,通过熟练掌握这些内容,学习者能够更自信地进行日常生活和课堂上的简单英语交流。通过不断地练习和应用,这些基础句子将成为流畅沟通的关键。
"和"The bigger one is mine." 总结来说,这个精品课件提供了全面的英语口语实践素材,覆盖了日常生活和学习中的常见情境,有助于提升英语口语表达和听力理解能力,对于英语学习者来说是极其宝贵的资源。通过反复...
一本英文书
### 健身小册子《Bigger Leaner Stronger》关键知识点解析 #### 一、书籍概述 《Bigger Leaner Stronger》是一本由Michael Matthews编写的健身指南,旨在帮助读者通过科学的方法实现理想的体型。本书由Waterbury ...
- 双写末尾字母加er,如big → bigger。 8. 比较级的注意事项: - 比较的两者必须是同类事物,具有可比性。 9. 比较级专项练习: - 请根据题目选择合适的形容词填空,如heavy, tall, long, big等。 10. 动词...
适用于Android和Java Final Project的Gradle 在此项目中,您将创建具有多种风格的应用程序,该应用程序使用多个库和Google Cloud Endpoints。 完成的应用程序将包含四个模块。 提供笑话的Java库,为这些笑话提供...
- 表示存在时,单数名词前使用 `there is`,例如 `There is a cat on the chair.`。 - 复数名词前使用 `there are`,例如 `There are many birds in the sky.`。 5. **some/any的使用**: - 肯定句中使用 `some`...
具体描述可以是“The bigger one.”或“The one on your right.”;询问多件物品归属时可以问“Are these books all yours?”;部分归属的回答可以是“Some of them are mine.” ### Identifying People辨别身份 ...
"Competition: Who is Smarter?"环节是一种互动教学方法,鼓励学生通过比较级进行智力竞赛。这个环节涵盖了各种形容词,如"small"、"thin"、"tall"、"beautiful"等,以及它们对应的比较级,如"smaller"、"thinner"、...
The bigger one." 通过以上六个情景的学习,英语口语的实践能力将得到显著提升,不仅适用于日常生活,也适合在特定场合如学校和工作环境中使用。掌握这些基本语句,将为你的英语沟通打下坚实的基础,助你在各种...
- 对于以辅音字母加元音字母加辅音字母结尾的形容词,需要双写末尾的辅音字母再加 `-er`,如 `big` 变为 `bigger`,`thin` 变为 `thinner`。 2. **不规则变化的形容词**: - 有些形容词的比较级和最高级是不规则...
3. (1) three years older (2) This tree is taller (3) You are four centimeters shorter (4) Who is heavier? 4. (1) How tall are you? (2) How old are you? 这些练习旨在巩固学生的词汇记忆,理解并熟练运用...
3. 在练习题I中,我们需要根据题目给出的比较关系填写适当的形容词比较级,例如 "The black dog is thinner than the white dog.","This balloon is bigger than yours.","My bag is heavier than yours.","John ...
吉蒂特·比格(Gitit Bigger) Gitit Bigger:基于Git和Markdown的Wiki,Bootstrap,ace编辑器,语法突出显示和docker部署支持。基于Git和Markdown的超棒的Wiki系统,Bootstrap,Ace编辑器等增强,支持Docker部署。...
5. Whose pencil-box is bigger, yours or hers? Hers is. 6. Mary’s hair is as long as Lucy’s. 7. Ben jumps higher than some of the boys in his class. 8. Does Nancy sing better than Helen? Yes, she ...
tenforflow_convolutional_bigger_dropout,卷积
5. "My backpack is bigger than you."中的"you"应改为"yours",比较的是背包,而不是人,因此用名词性物主代词"yours"。 在给出的练习题中,我们也看到了对"both"和"all"、"many"和"much"等词的区分。例如,"both...