Sep 5, 2011

Best Cow Line (POJ 3617)

You actually can solve the problem No. 3617 in POJ, Peking University Judge Online, with the greedy algorithm.

The author of "Programming contest challenge book" says that the greedy algorithm is effective for a problem that deal with dictionally order.

Here is more simple description of POJ 3617.

- - - - -


Description:
You have a string S that length is N and make a string T that length is N. At the beginning, length of S is zero. You can do either operation from below:

 - delete the first character of S and add it into the end of T
 - delete the last character of S and add it into the end of T

Make T as small as in dictionary order.

Constraint:
1 <= N <= 2000
string s can contain small alphabet.

Sample Input:
N = 6
S = "ABCDBCB"

Sample Output:
ABCBCD

My Solution:
https://github.com/yohei1126/pccb/blob/master/beginner/search/GreedyAlgorithm/BestCowLine/BestCowLine.cpp

No comments:

Post a Comment