[Need Help] Yet another DP problem!

Правка en3, от ivplay, 2017-11-30 18:10:26

Original Statement https://community.topcoder.com/stat?c=problem_statement&pm=13268&rd=16187
Problem Summary : Given an array of 1<=N<=47 integers. All the integers are in range [1,47]. Given two number low,high(1<=low<=high<=47). We have pick a sub sequence of the given array in minimum move that contains only the numbers in range [low,high] and all the numbers in range[low,high]. In a single move we can pick a continuous sequence of numbers from the given array. We to find number of ways to pick such sub sequence in minimum move.
Examples
First line contains the integers. Second and third line contains value of low and high respectively.
(Case 0)
{2, 1, 3}
1
3
Returns: 1
The only way to choose the subset is to choose all animals.
(Case 1)
{3, 4, 1, 3, 4, 2}
1
3
Returns: 2
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, animal #5 forms the other.
(Case 2)
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2
6
Returns: 2
(Case 3)
{3, 1, 4}
2
4
Returns: -1
(Case 4)
{2, 1, 3, 1, 4}
1
4
Returns: 1
Note that we are not required to minimize the number of animals we send. Here, we could select just four of these five animals but that would create two groups. A better solution is to select all five animals, then they all form a single group.
(Case 5)
{7, 12, 2, 12, 10, 13, 6, 5, 3, 3, 4, 11, 12, 4, 3, 1, 8, 11, 4, 7, 6, 5, 47}
2
7
Returns: 3 Don't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.

Теги dynamic programming, topcoder, idea, number of ways

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский ivplay 2017-11-30 18:13:21 8 Tiny change: 'rns: 3 Don't figure' -> 'rns: 3 I couldn't figure'
en4 Английский ivplay 2017-11-30 18:11:41 5 Tiny change: 'array. We to find n' -> 'array. We need to find n'
en3 Английский ivplay 2017-11-30 18:10:26 34 Tiny change: 'https://co' -> 'Original Statement https://co'
en2 Английский ivplay 2017-11-30 18:09:42 283
en1 Английский ivplay 2017-11-30 18:04:54 1463 Initial revision (published)