Блог пользователя praveenojha33

Автор praveenojha33, история, 5 лет назад, По-английски

Can anyone tell me how I can proceed to solve this problem https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4108 . ( I am unable to find any good content which explains the solution of this problem. ) Thank You. Updated Link of the problem:https://uva.onlinejudge.org/external/13/1362.pdf

Теги dp, uva
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by praveenojha33 (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Suppose the input sequence is S, d(i,j) is the number of trees corresponding to the subsequences Si,Si+1,...,Sj, you can find d(i,i)=1; and Si is not equal to Sj d (i,j)=0 (because the start point and end point should be the same point). In other cases, suppose the first branch returns to the root of the tree at Sk (there must be Si=Sk), then the sequence corresponding to this branch is Si+1...Sk-1, and the number of solutions is d(i+1,k -1); The access sequence corresponding to other branches is Sk,...Sj, and the number of solutions is d(k,j). Thus, in a non-boundary situation, the recursive relationship is;

d(i,j)=sigma{d(i+1,k-1)*d(k,j)|i+2<=k<=j,Si=Sk=Sj}.

Explanation translated from : Explanation Solution code : Solution