BadNeighbors - 2004 TCCC Online Round 4 - Division I, Level One

dp_3.py

# https://community.topcoder.com/stat?c=problem_statement&pm=2402&rd=5009
#
# 状态转移方程:
#
# max{
#      max{m[i-1][0], m[i-2][0] + A[i-1]},
#      max{m[i-1][1], m[i-2][1] + A[i]}
#    }
#

class BadNeighbors:
    def maxDonations(self, donations):
        length = len(donations)

        # len <= 3
        if length < 4: return max(donations)

        # len >= 4
        # [i][0] means max from 0..i-1
        # [i][1] means max from 1..i
        matrix = [[0]*2 for i in range(length)]

        matrix[0][0] = donations[0]
        matrix[0][1] = donations[0]

        matrix[1][0] = donations[0]
        matrix[1][1] = donations[1]

        matrix[2][0] = max(donations[0:2])
        matrix[2][1] = max(donations[1:3])

        for i in range(3, length):
            matrix[i][0] = max(matrix[i-1][0], matrix[i-2][0] + donations[i-1])
            matrix[i][1] = max(matrix[i-1][1], matrix[i-2][1] + donations[i])

        return max(matrix[-1][0], matrix[-1][1])


if __name__ == '__main__':
    A = (10, 3, 2, 5, 7, 8)
    # A = (11, 15)
    # A = (7, 7, 7, 7, 7, 7, 7)
    # A = (1, 2, 3, 4, 5, 1, 2, 3, 4, 5)
    # A = (94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61,
         # 6, 237, 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397,
         # 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72)

    badNeighbors = BadNeighbors()
    print(badNeighbors.maxDonations(A))