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

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

Hello Codeforces .

Plase help.

Given n, array a(a1, a2,,, an). n, a[i] <= 100.

How can i make dp[i][j].

Corectly dp[i][j] = 1, if we can get sum j without a[i].

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

How can you say its easy if you are stuck in it and asking for help? :/

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

    it is easy for some people

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

      I have thought of a solution.

      Take dpt[j] be the number of ways you can make the sum j using any elements. So, for each sum from 1 to 10000, you take each of the a[i] into consideration and do a dpt[sum-a[i]]++.

      Now, dp[i][j] is 1 if dpt[j]>=2 or else its 0.

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

What are the constraints on n ?

If you don't mind, can you put a link to the exact question. This is kind of hard to understand.

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

Calculate DP for prefixes and suffixes. Now, DP[i][j] = 1 if there exists A and B such that A+B=j and A is obtained as sum from prefix and B is obtained as sum from suffix.