DP T

Counting up how many ways there are to arrange numbers to satisfy a given size relationship

Is it a DP that takes "the set of numbers we haven't used yet" as its domain?

Impossible because the size of the set is 3000 and large.

Can we narrow the definitional area by equating something with something else?

https://gyazo.com/cf77e332e55be1555ffab63ac2e210de

There are still "three options" in either of these two situations.

So, "how many are greater than or less than the number selected immediately before" is the domain of definition

Where is the end of the search?

With one number remaining.

DP that enumerates "1 remaining state" in advance and then finds "k remaining states using the values of k-1 remaining states".

https://gyazo.com/15d46557ea961335ad637bf01a487a4a

First, make the code work correctly when N=2.

code:python

def solve(N, lessthan):

# init

# f("<", lower=0, upper=1) = 1, f("<", 1, 0) = 0

k = 1

for i in range(k + 1):

else:

for i in range(k + 1):

return sum(table)

Then make the code work correctly when N=3

code:python

def solve(N, lessthan):

k = 1

for i in range(k + 1):

else:

for i in range(k + 1):

if N > 2:

k = 2

for i in range(k + 1):

for j in range(k - i):

else:

for i in range(k + 1):

for j in range(i):

table = newtable

return sum(table)

Then extend to general N.

Now all the sample code goes through.

TLE when submitting

code:python

def solve(N, lessthan):

k = 1

for i in range(k + 1):

else:

for i in range(k + 1):

for k in range(2, N):

for i in range(k + 1):

for j in range(k - i):

else:

for i in range(k + 1):

for j in range(i):

return sum(table) % MOD

Since the loop is a range sum, we can use cumulative summing to speed up the process.

code:python

for k in range(2, N):

for i in range(k + 1):

# for j in range(k - i):

else:

for i in range(k + 1):

# for j in range(i):

---