这个问题用线段数还是用动态规划?回溯算法怎么实现?

Problem Description

In the year 8888, the Earth is ruled by the PPF Empire . As the population growing , PPF needs to find more land for the newborns . Finally , PPF decides to attack Kscinow who ruling the Mars . Here the problem comes! How can the soldiers reach the Mars ? PPF convokes his soldiers and asks for their suggestions . “Rush … ” one soldier answers. “Shut up ! Do I have to remind you that there isn’t any road to the Mars from here!” PPF replies. “Fly !” another answers. PPF smiles :“Clever guy ! Although we haven’t got wings , I can buy some magic broomsticks from HARRY POTTER to help you .” Now , it’s time to learn to fly on a broomstick ! we assume that one soldier has one level number indicating his degree. The soldier who has a higher level could teach the lower , that is to say the former’s level > the latter’s . But the lower can’t teach the higher. One soldier can have only one teacher at most , certainly , having no teacher is also legal. Similarly one soldier can have only one student at most while having no student is also possible. Teacher can teach his student on the same broomstick .Certainly , all the soldier must have practiced on the broomstick before they fly to the Mars! Magic broomstick is expensive !So , can you help PPF to calculate the minimum number of the broomstick needed .
For example :
There are 5 soldiers (A B C D E)with level numbers : 2 4 5 6 4;
One method :
C could teach B; B could teach A; So , A B C are eligible to study on the same broomstick.
D could teach E;So D E are eligible to study on the same broomstick;
Using this method , we need 2 broomsticks.
Another method:
D could teach A; So A D are eligible to study on the same broomstick.
C could teach B; So B C are eligible to study on the same broomstick.
E with no teacher or student are eligible to study on one broomstick.
Using the method ,we need 3 broomsticks.
……

After checking up all possible method, we found that 2 is the minimum number of broomsticks needed.

Input
Input file contains multiple test cases.
In a test case,the first line contains a single positive number N indicating the number of soldiers.(0<=N<=3000)
Next N lines :There is only one nonnegative integer on each line , indicating the level number for each soldier.( less than 30 digits);

Output
For each case, output the minimum number of broomsticks on a single line.

Sample Input
4
10
20
30
04
5
2
3
4
3
4

Sample Output
1
2

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

0
Galou is back! 类欧几里得算法 线段树方面的一个问题的思路求教,怎么利用C语言的编写实现
0
整数线段树规划的问题,如何利用C语言编程解决实现
0
一个时间方面的区间线段的问题的办法,怎么解决这个问题用到C语言的办法
0
曲线线段距离求和算法的一个判断,采用C语言编程语言的实现的方式
0
二进制线段数列的枚举的典型问题,使用C语言编写程序设计解决这个算法是怎么做的
0
线段编码应该怎么编号,这个题目使用C程序设计语言怎么实现的
0
区域线段的算法的问题的一种题目,怎么利用C语言的程序的编写的技巧来实现?
0
圆周上交叉的线段的结点的问题,怎么利用C语言的程序的编写的实现的思路?
0
算法问题用线段如何构成三角形,怎么利用C语言的程序的代码的编制实现程序?
1
Qt Qchart绘制的曲线怎么在鼠标点击时添加2条竖分割线来选取线段
0
线段在圆周上交叉点的问题,怎么才能使用C语言的编写程序的知识的办法去实现的呢?
0
线段搜索寻找答案的最大的值,怎么采用C语言的程序办法思想去实现呢,具体的代码实现?
0
区间线段的搜索问题的综合运用,怎么使用C语言的程序编写的程序的格式来实现算法的解答
0
圆和直线线段的焦点和相切,怎么使用C语言的程序的代码编写的办法有效地实现的过程是什么
0
计算圆形和线段的切线的问题,要求是使用C语言的程序的代码设计的编写的过程如何加以实现的呢
0
线段 的计算问题
0
Shoring Up the Levees 线段坐标的计算问题
0
线段处理 算法程序的实现
0
线段处理 的实现的问题
1
关于算法的一个小问题