题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1108

解题报告:

1、首先按照weight从小到大排列,weight相同的按照speed从大到小排列;

2、Count[i]表示到第i个老鼠时,所求的最长“速度递减”子序列的长度;

3、path[i]=j是题目的关键,记录在Count[i]=Count[j]时,即最长“速度递减”子序列最后一个老鼠的前一只老鼠的位置

4、递归输出id

void output(int path[],pos)
{
if(pos==) return ;
output(path,path[pos]);
printf("%d\n",mice[pos].id);
}

Sources Code:

#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f using namespace std; int n;///n只老鼠
int Count[]= {}; ///count[i]表示构造到第i个老鼠时,序列的最大长度
int path[]= {}; ///path[i]表示构造到第i个老鼠时的前一个老鼠(前驱) struct mouse
{
int weight;
int speed;
int id;
} mice[]; int cmp(const void *a,const void *b)
{
struct mouse *p1=(mouse *)a;
struct mouse *p2=(mouse *)b;
if(p1->weight==p2->weight)
{
if(p1->speed>p2->speed)
return p2->speed-p1->speed;
else return p1->speed-p2->speed;
}
else return p1->weight-p2->weight;
} void output(int path[],int pos)
{
if(pos==) return ;
output(path,path[pos]);
printf("%d\n",mice[pos].id);
} int main()
{
n=;
int i=,j=;
while(scanf("%d%d",&mice[++i].weight,&mice[++j].speed)!=EOF)
{
n++;
mice[n].id=n;
}
qsort(mice+,n,sizeof(mice[]),cmp);
Count[]=;
for(int i=; i<=n; i++)
{
for(int j=; j<i; j++)
{
if(mice[i].weight>mice[j].weight&&mice[i].speed<mice[j].speed)
{
if(Count[i]<Count[j])
{
Count[i]=Count[j];
path[i]=j;
}
}
}
Count[i]++;
}
int _max=;
int pos;
for(int i=; i<=n; i++)
{
if(Count[i]>_max)
{
_max=Count[i];
pos=i;
}
}
printf("%d\n",_max);
output(path,pos);
}

最新文章

  1. Euler猜想
  2. ionic 发送请求返回一直都是404
  3. cf.301.D. Bad Luck Island(dp + probabilities)
  4. 获取shell脚本自身所在目录的Shell脚本分享
  5. C# HttpHelper 采集
  6. 判断字符串中是否有SQL攻击代码
  7. JS初学之-for套for遍历二维数组
  8. AngularJs学习笔记-慕课网AngularJS实战
  9. ios Swift 特性
  10. kernel_task占用大量CPU
  11. 对 Azure Backup 的常见配置问题进行故障排除
  12. 打造你的办公环境-email篇
  13. 如何创建并运行java线程
  14. 基于Ado.Net的日志组件
  15. javaIO流实现文件拷贝
  16. 可迭代对象 TO 迭代器
  17. (a ==1 &amp;&amp; a== 2 &amp;&amp; a==3) 有可能是 true 吗?
  18. 解决编译错误:cc: Internal error: Killed (program cc1)
  19. python--Numpy简单实用实例
  20. Phpcms v9专题分类增加模板设置的方法

热门文章

  1. Mercedes BENZ C5 SD Connect Xentry Tab Kit Technical Support
  2. java 简单的des加密示例
  3. 多重if 与 switch case的区别
  4. Android多语言与国际化
  5. TCP-Java--图谱
  6. python网络编程——简单例子
  7. php 项目中自定义日志方法
  8. 04.Path类的学习
  9. 03.if 和 switch结合练习
  10. Wp及Windows应用商店程序Logo生成器