praveenojha33's blog

Help needed for Exploring Pyramid Problem on UVa ( UVa 1362 )
By praveenojha33, history, 5 years ago, In English

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

Tags dp, uva
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply