Simulation Contest 2 Solutions

Current Progress: Linear DP, Knapsack Problems, Intervals

Challenging Problems

1038 [NOIP2008] Paper Passing

Tags

High-Dimensional DP

Approach

1. The challenge lies in ensuring that the path from (1,1) to (n,m) and back from (n,m) to (1,1) do not overlap. It can be treated as finding two non-overlapping paths from (1,1) to (n,m) with maximum kindness sum. Define dp[i][j][k][l] as the maximum kindness sum when the first path reaches (i,j) and the second path reaches (k,l). Ensure that i != k and j != l for valid transitions.
2. Time complexity is O(n^2m^2).

Code

Similar Problem - 1039 [NOIP2000] Grid Taking Numbers

1041 [NOIP2010] Turtle Chess

Tags

High-Dimensional DP

Approach

1. The key is to track the usage of cards. Define dp[i][j][k][l] as the maximum score achievable using i cards of type 1, j of type 2, k of type 3, and l of type 4.
2. Time complexity is O(product of num_i), where num_i represents the count of each card type.

Code

1042 To the Max

Tags 1

Prefix Sum

Approach

1. Calculate the 2D prefix sum and brute-force iterate over the top-left and bottom-right corners of the rectangle.
2. Time complexity is O(n^4).

Tags 2

DP Prefix Sum

Approach 2

1. Iterate over the top and bottom rows. Since the columns are continuous, define dp_k as the maximum sum ending at column k for rows i and j. Use prefix sums for efficiency.
2. Time complexity is O(n^3).

Code 2

1043 [ZJOI2007] Chessboard Production

Tags

DP Line Method Greedy

Approach

1. A standard problem involving the line method for DP.

Code

1034 [USACO 2009 Dec G] Video Game Troubles

Tags

State Separation Discussion DP

Approach

1. State separation discussion involves separating states that can be discussed independently without affecting the correctness of state transitions.
2. Define dp[i][j] as the maximum value achievable by selecting from the first i game consoles with j money. Discuss purchasing consoles first, then discuss selecting games within a console, and finally discuss not purchasing the console.
3. Time complexity is O(nmk).

Code

1048 [NOIP2007] Watcher's Escape

Tags

State Separation Discussion DP Greedy

Approach

1. It is easy to see that not using the flash magic and moving at 17m/s is independent of the magic points. This can be handled separately.
2. Consider using the flash magic. According to greedy principles, use it when enough magic points are available, otherwise add magic points and continue.
3. Add the normal movement state separately.

Code

1044 [SCOI2005] Maximum Submatrix

Tags

State Separation Discussion DP

Approach

1. First transpose the matrix, which does not affect the answer.
2. If the matrix has only one row, define dp[i][j] as the maximum value achievable by selecting j matrices from the first i columns. dp[i][j] = max(dp[i-1][j], dp[p-1][j-1] + sum[i] - sum[p-1]).
3. If the matrix has two rows, inspired by the one-row approach, define dp[i][j][k] as the maximum value achievable by selecting k matrices from the first i columns of the first row and j columns of the second row. Consider cases where the first or second row participates in the k-th matrix selection, and ensure i = j when both rows participate.

Code

Similar Problem - 1038 [NOIP2008] Paper Passing

1049 [NOIP2018] Currency System

Tags

Statistical DP Thinking

Approach

1. The breakthrough point is realizing that two currency system are equivalent if they can express each other. Find the simplified currency system by selecting numbers from the original system that can express any number in the original system.
2. Clearly, smaller numbers cannot be expressed by larger ones. The large number must be a linear combination of smaller ones. Sort the numbers in ascending order and use dp[i][j] to represent whether the first i-1 numbers can express j. Add numbers that cannot be expressed to the new system.

Code

Similar Problems - 1051 [HAOI2012] Volume Adjustment, 1050 [USACO 1050 2009 Oct G] Bessie's Weight Problem

1046 [USACO 2016 Open P] 262144

Tags

Doubling DP Statistical DP

Approach

1. Interval DP can be used but the time complexity O(n^2) is not acceptable.
2. The difficulty in state transfer is not knowing the origin of a number or its exact value. Define dp[i][j] as the value of the interval starting at j and ending at dp[i][j]. Initialize dp[a_i][i] = i, and when dp[i][j] = 0, use the transfer equation dp[i][j] = [dp[i-1][dp[i-1][j]+1] != 0]. This is called doubling DP due to the similarity of the transfer equation.

Code

1040 [NOIP2005] River Crossing

Tags

Path Compression

Approach

1. Because the frog's path has a cycle lcm(S,T), and ST >= lcm(S,T), if the distance between two adjacent stones is greater than 2ST, it can be adjusted to 2S*T. Special handling is required for the case where S == T.

Code

1036 Convex Polygon Division

Tags

Mathematics Interval DP

Note

Do not assume that only lines from one vertex can divide an N-gon into N non-overlapping triangles.

Code

dp = [[10**40 for _ in range(n)] for _ in range(n)] for i in range(n): if i + 2 < n: dp[i][i+2] = a[i] * a[i+1] * a[i+2] if i + 1 < n: dp[i][i+1] = 0 if i < n: dp[i][i] = 0

def cal(x, y, z): if x == y or x == z or y == z: return 0 return a[x] * a[y] * a[z]

for li in range(4, n+1): for l in range(n): r = l + li - 1 if r >= n: break for p in range(l+1, r): dp[l][r] = min(dp[l][r], dp[l][p] + dp[p][r] + cal(l, r, p))

print(dp[0][n-1])

</details>