雪黛依梦
幸福的飞翔——简单世界
C++博客
首页
新随笔
联系
聚合
管理
posts - 99, comments - 8, trackbacks - 0
hdu 1160 简单题
//解题思路:根据题意,要输出的是排序之前的序号,所以将要处理的数据都存入一个结构体中
//首先利用qsort对weight进行快排
//剩下的问题就是从已排好的数组中找到最长下降子列(speed),并且输出这个子列的长度和子列中的元素的下标
#include <stdio.h>
#include <stdlib.h>
struct mouse
{
int w;
int s;
int cn;
}node[1001];
int cmp (const void *a, const void *b) //一定要注意指针的指向是结构体 mouse
{
if ( (*(mouse *)a).w != (*(mouse *)b).w ) //体重不等时对体重进行排序
return (*(mouse *)a).w - (*(mouse *)b).w;
else if ( (*(mouse *)a).w == (*(mouse *)b).w )
return (*(mouse *)b).s - (*(mouse *)a).s; //反之对速度进行降序排序
}
int main ()
{
//输入数据
int levl = 1;
while (scanf ("%d%d", &node[levl].w, &node[levl].s) != EOF)
{
node[levl].cn = levl;
levl ++;
}
//快排
qsort ( node, levl, sizeof(node[0]), cmp );
//对speed 按降序找到最长的子串:
//用数组F[i]记录以i为起点的满足条件的子列长度,显然初始时为1;
//用rout[i]记录搜索到最长子串的路径 ,把路径的下标存入到index[]中
//max记录到当前为止子列的最长长度,end 记录到当前为止最长子列的最后一个下标
int F[1001];
for (int i = 1; i < levl; i ++)
{
F[i] = 1;
}
int rout[1001];
for (int i = 1; i < levl; i ++)
{
rout[i] = i;
}
int max = 1; int end = 1;
for (int i = 2; i < levl; i ++)
{
for (int j = 1; j < i; j ++)
{
if (node[j].s > node[i].s)
{
if (F[j] + 1 > F[i]) //现在长度增加1要 > 当前F[i] 才能产生作用
{
F[i] = F[j] + 1;
rout[i] = j; //记录找到最下降序列的路径(即下标标号)
}
}
}
if ( F[i] > max ) //当前记录的长度大于 > max时
{
max = F[i];
end = i;
}
}
printf ("%d\n", max);
int index[1001];
for (int i = 0; i < max; i ++) //将路径记录到数组index[]中
{
index[max - i - 1] = end;
end = rout[end--];
}
for ( int i = 0; i < max; i ++)
{
printf ("%d\n", node[index[i]].cn);
}
// system ("pause");
return 0;
}
posted on 2010-08-22 11:24
雪黛依梦
阅读(988)
评论(0)
编辑
收藏
引用
所属分类:
动态规划
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
hdu 1160 简单题
hdu 1466 DP 直线的可能交点数目
hdu 1087 DP
grids 2757 求最大子例长度
hdu 2050 折线分割平面
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
<
2010年8月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(4)
给我留言
查看公开留言
查看私人留言
随笔分类
HTML(1)
JAVA--J2SE(5)
QT
背包----贪心、回溯、分支界限(5)
并查积(3)
博弈(6)
大数(7)
动态规划(5)
哈希法(4)
技巧题(1)
简单题(15)
考研相关(5)
蛮力(1)
模拟题(1)
母函数(3)
排序题(2)
求最短路径(1)
数论(11)
数学题(1)
搜索---DFS BFS(1)
字典树(1)
字符串处理题(6)
最小生成树(4)
随笔档案
2011年8月 (1)
2011年7月 (9)
2011年3月 (3)
2010年11月 (3)
2010年9月 (12)
2010年8月 (71)
文章档案
2010年8月 (1)
搜索
最新评论
1. re: hdu 1211 数论
你做的什么啊,数据弱让你过了@Lysander
--44
2. re: 全国34所计算机研究生录取分数线
全国34所计算机研究生录取分数线 ?
--王丹
3. re: hdu 1005
递归想都不要想?矩阵乘法+快速幂不高兴
--WonderMan
4. re: hdu 1085
评论内容较长,点击标题查看
--Dack Sword
5. re: hdu 1085
弱弱的说一句,你这个代码是有问题,刚刚我试了,WA了,以前OJ的数据太弱了,侥幸通过了额
--Dack Sword
阅读排行榜
1. Floyd算法详解:求解任意两点间的最短距离(12868)
2. 生产者消费者问题(wait、notify、 notifyAll用法示例)(2660)
3. 全国大学计算机专业排名(转贴)((2316)
4. ZOJ 3197 贪心 最小区间覆盖问题(2283)
5. poj 1001(1891)
评论排行榜
1. hdu 1085(2)
2. hdu 1211 数论(2)
3. 全国34所计算机研究生录取分数线 (1)
4. hdu 1005(1)
5. 中国剩余定理(1)