题目大意:读入一些数(每行读入$w[i],s[i]$为一组数),要求找到一个最长的序列,使得符合$w[m[1]] < w[m[2]] < ... < w[m[n]]$且$s[m[1]] > s[m[2]] > ... > s[m[n]]$,并输出每组数在读入时的顺序具体见原题目

思路:先根据w从小到大排序,再求最长下降子序列,DP时保存路径,最后递归输出路径。

C++ Code:

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int n=1;
struct sz{
int w,s,num;
bool operator <(const sz& rhs)const{
if(w!=rhs.w)return w<rhs.w;
return s>rhs.s;
}
}a[1020];
int d[1020],p[1020];
void dg(int n){
if(n==0)return;
dg(d[n]);
printf("%d\n",a[n].num);
}
int main(){
while(scanf("%d%d",&a[n].w,&a[n].s)!=EOF)a[n].num=n,n++;
n--;
sort(a+1,a+n+1);
memset(d,0,sizeof(d));//d[i]表示i的前一个数
memset(p,0,sizeof(p));//p[i]表示以s[i]结尾的最长下降子序列的长度
for(int i=1;i<=n;i++)p[i]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++)
if(a[i].w>a[j].w&&a[i].s<a[j].s){//a[i].w>a[j].w不能去掉,因为可能出现两个w相等的情况
if(p[i]<p[j]+1){
p[i]=p[j]+1;
d[i]=j;
}
}
}
int t,max=0;
for(int i=1;i<=n;i++)
if(max<p[i]){
t=i;
max=p[i];
}
printf("%d\n",max);
dg(t);
return 0;
}

最新文章

  1. jQuery验证控件jquery.validate.js使用说明+中文API
  2. Bootstrap&lt;基础一&gt; CSS 概览
  3. 似乎都设置了utf-8,为什么出现乱码
  4. 如何杀掉D状态的进程?[zt]【转】
  5. C# 类的多态、结构、接口、抽象、虚函数总结
  6. Queue and Message
  7. Redis系统学习 四、超越数据结构
  8. 用cas来实现php的单点登陆
  9. dialog使用方法(同一页面,调用一个js代码,实现多个不同样式的弹窗)
  10. Linux文件锁定保护命令chattr介绍
  11. 动态创建 script 实现跨域请求数据
  12. Frame buffer分析 - fbmem.c【转】
  13. MySQL中间件之ProxySQL(9):ProxySQL的查询缓存功能
  14. BZOJ3772 精神污染 主席树 dfs序
  15. 【MySQL (六) | 详细分析MySQL事务日志redo log】
  16. immutable.js使用总结
  17. Android padding 和margin
  18. 设计模式之迭代器模式(Iterator Pattern)
  19. 腾讯云Mac图床插件
  20. 每日一问(如何在List中加入、设置、获取和删除其中的元素?)

热门文章

  1. 【BZOJ3600】没有人的算术 - 替罪羊树+线段树
  2. web前端对文件的引用规则
  3. android onConfigurationChanged的那点事
  4. swiper.js在隐藏/显示切换时,轮播出现bug的解决办法
  5. Updates were rejected because the remote contains work that you do(gitee报错解决方案)
  6. 启动 Appium 自带模拟器
  7. Spring 让 LOB 数据操作变得简单易行
  8. 多播 &amp; multicast
  9. linux 下password加密程序(能够用于替换shadow文件里的用户password)
  10. Bootstrap警告