|
|
back to boardCommon BoardWho can give me a hint on problem 1183 or how I can improve my algortihm(+) I have a dynamic algorithm O(n^3).I use a structer
Answer : array[1..100,1..100,1..100]of String;
But it too large! Answer[k,i,j] - is the regular sequence with
minimum length,in which copy(S,1,k) contained (where S - sequnce in
input) I use FullSearch and get Accepted! But I need a good algorithm. Who can help me?(-) > I have a dynamic algorithm O(n^3).I use a structer
> Answer : array[1..100,1..100,1..100]of String;
> But it too large! Answer[k,i,j] - is the regular sequence with
> minimum length,in which copy(S,1,k) contained (where S - sequnce in
> input) Re: Who can give me a hint on problem 1183 or how I can improve my algortihm(+) > I have a dynamic algorithm O(n^3).I use a structer
> Answer : array[1..100,1..100,1..100]of String;
> But it too large! Answer[k,i,j] - is the regular sequence with
> minimum length,in which copy(S,1,k) contained (where S - sequnce in
> input)
Just use DP : D[i,j] is the minimum number of additional chacracters
to obtain the right sequence. We can use this table to get the
minimum sequence. |
|
|
