|
|
back to boardSome hints needed. Can somebody give hints to solve this task? Re: Some hints needed. Posted by svr 8 Oct 2011 19:06 Conflict graph may help. Positions of possible substrings are vertices and two positions conflict if they can not be simultaneously. Answer= max number of independent vertices. Also let relation a<b means that position is before of position b and they don't conflict.Then a<b,b<c=> a<c so we have an order. Answer is a height of ordered structure. Edited by author 08.10.2011 19:07 Re: Some hints needed. Just easy DP. Re: Some hints needed. Posted by svr 10 Oct 2011 11:47 But Dp may be difficult- problem of 35 test. When poset is used and standard dfs for it's height we have Ac without any problems. |
|
|