文档章节

hdoj_1160FatMouse's Speed

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:43
字数 503
阅读 36
收藏 0

FatMouse's Speed

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5806    Accepted Submission(s): 2504
Special Judge


Problem Description
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.
 

Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed. 
 

Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],..., m[n] then it must be the case that 

W[m[1]] < W[m[2]] < ... < W[m[n]]

and 

S[m[1]] > S[m[2]] > ... > S[m[n]]

In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one. 
 

Sample Input

   
6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900
 
Sample Output

   
4 4 5 9
7 //=.=
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Point{
	int weight;
	int speed;
	int num;
	int pre;
}mice[1005];

bool cmp(Point a, Point b)
{
	if(a.weight == b.weight) return a.speed > b.speed;
	else return a.weight < b.weight;
}

//void output(int k)
//{
//	if(k<=0) return;
//	output(mice[k].pre);
//	cout<<mice[k].num<<endl;
//}

int main()
{
	freopen("E:\\ACM\\HDOJ\\hdoj_1160\\in.txt","r",stdin);
	int i, j, v = 1, flag, max;
	int dp[1005] = {0};
	while(scanf("%d %d", &mice[v].weight, &mice[v].speed)!=EOF)
	{
		mice[v].num = v++;
	}
	v--;
	sort(mice+1, mice+v+1, cmp);

	max = 0;
	for(i = 1; i <= v;  i++)
	{
		dp[i] = 1;
		for(j = 1; j < i; j++)
		{
			if(mice[i].weight > mice[j].weight && mice[i].speed < mice[j].speed && dp[j] +1 > dp[i] )
			{
				dp[i] = dp[j] + 1;
				mice[i].pre = j;
				if(dp[i] > max)
				{
					max = dp[i];
					flag = i;
				}
			}
		}
	}

	cout << max << endl;
	int ans[1005];
	j = 1;
	for( i = 1; i <= max; i++)
	{
		ans[j++] = mice[flag].num;
		flag = mice[flag].pre;
	}
	for( i = max; i >= 1; i--)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}


© 著作权归作者所有

上一篇: JSON样例
下一篇: html作业记录
N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
反素数求解及相关题目

反素数 定义:对于任何正整数n,其约数个数记为f(n),例如f(6)=4;如果存在一个正整数n满足:对于任意的正整数x(0

my_sunshine26
2017/05/26
0
0
hdoj 1020 Encoding

EncodingTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 52209 Accepted Submission(s): 23212 include int main(){//freopen("t......

dear_jia
2018/04/23
0
0
HDOJ 1009 FatMouse' Trade

FatMouse' TradeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 81301 Accepted Submission(s): 28137 Problem Description FatM......

Dear_Jia
2017/09/30
0
0
HDOJ4548美素数

美素数Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 7741 Accepted Submission(s): 2714 Problem Description   小明对数的研......

zhagoodwell
2017/12/11
0
0
HDOJ 1811 Rank of Tetris

Rank of TetrisTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11206 Accepted Submission(s): 3206 Problem Description 自从L......

dear_jia
2018/04/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
43分钟前
3
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
2
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
3
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部