Problem A: Bus to Pénjamo
Problem B: Kar Salesman
Problem 3: Gerrymandering
For each DP state, the following transitions are possible:
From
dp[k][0]
: dp[k+3][0] = max(dp[k+3][0], val + vot) # move 3 columns forward dp[k+1][1] = max(dp[k+1][1], val + vot) # move 1 column forward, leave an extra cell in the first row dp[k+1][2] = max(dp[k+1][2], val + sum) # move 1 column forward, leave an extra cell in the second rowFrom
dp[k][1]
: dp[k+3][1] = max(dp[k+3][1], val + vot) # continue filling with a vertical piece in the first row dp[k+2][0] = max(dp[k+2][0], val + sum) # fill the second row and move 2 columns forwardFrom
dp[k][2]
: dp[k+3][2] = max(dp[k+3][2], val + vot) # continue filling with a vertical piece in the second row dp[k+2][0] = max(dp[k+2][0], val + sum) # fill the first row and move 2 columns forward
To implement the DP solution, you only need to handle the transitions for states dp[i][0]
and dp[i][1]
. For dp[i][2]
, the transitions are the same as dp[i][1]
, with the rows swapped.