杰拉斯的博客
[ACM_POJ_2533]Longest Ordered Subsequence
杰拉斯 | 时间:2012-04-03, Tue | 20,371 views编程算法
Longest Ordered Subsequence
(最长有序子序列)
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 21942 Accepted: 9441
Description
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.
[ACM_ZJUT_1029]斐波那契数列
杰拉斯 | 时间:2012-04-03, Tue | 17,823 views编程算法
Fibonacci数
Time Limit:1000MS Memory Limit:32768K
Description
有一些整数(≤46),输出以这些整数为序数的第n项fibonacci数。文件中的数据可能上万,但要求运行时间不超过1秒钟。
注:f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2).
Sample Input
5 6 7 8 9 40
Sample Output
5 8 13 21 34 102334155
[ACM_POJ_2081]动态规划入门练习(三)Recaman's Sequence
杰拉斯 | 时间:2012-04-03, Tue | 5,976 views编程算法
Recaman's Sequence
Time Limit: 3000MS Memory Limit: 60000K
Total Submissions: 17939 Accepted: 7450
Description
The Recaman's sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−1 + m.
The first few numbers in the Recaman's Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 ...
Given k, your task is to calculate ak.
Input
The input consists of several test cases. Each line of the input contains an integer k where 0 <= k <= 500000.
The last line contains an integer −1, which should not be processed.
Output
For each k given in the input, print one line containing ak to the output.
[ACM_POJ_1579]动态规划入门练习(二)Function Run Fun
杰拉斯 | 时间:2012-04-03, Tue | 22,460 views编程算法
Function Run Fun
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 12362 Accepted: 6466
Description
We all love recursion! Don't we?
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
[ACM_POJ_1163]动态规划入门练习(一)The Triangle
杰拉斯 | 时间:2012-04-02, Mon | 22,240 views编程算法
The Triangle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 28092 Accepted: 16504
Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.