wh1te_whale's blog

By wh1te_whale, history, 5 years ago, In English

Given an array of n integer elements. At a single moment we can delete a subarray if every element of this subarray is equal to one another. Doing so give us the points equal to (size of subarray)^2. We have to completely eliminate the array and also maximise the sum of points scored. How to solve this problem?

Score will change on the basis of order.

Eg:

Array = 11212

say it divided into 4 segments 11,2,1,2

If you choose order of segments as 3,(2,4),1. then score will be 1+4+4.

If you choose order of segments as 2,4,(1,3). then score will be 1+1+9.

amitgomi thanks for this example.

  • Vote: I like it
  • +17
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What are the constraints? Time Limit etc. ? Max.Size of array?

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

I think it is similar to 1132F - Clear the String

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You have to find order of those operations also to get solution of this problem.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      But he hasn't said this in the blog. How do you know. Are you both related

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

        Score will change on the basis of order.

        11212

        say it divided into 4 segments 11,2,1,2

        If you choose order of segments as 3,(2,4),1. then score will be 1+4+4.

        If you choose order of segments as 2,4,(1,3). then score will be 1+1+9.

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

        amitgomi explaied it right.

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

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