摘要
Title: 2786. 访问数组中的位置使分数最大
Tag: dp、状态机
Memory Limit: 64 MB
Time Limit: 1000 ms

2786. 访问数组中的位置使分数最大

题意

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你一开始在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

如果你当前在位置 i ，那么你可以移动到满足 i < j 的任意位置 j 。
对于你访问的位置 i ，你可以获得分数 nums[i] 。
如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的奇偶性不同，那么你将失去分数 x 。
请你返回你能得到的最大得分之和。

注意，你一开始的分数为 nums[0] 。

思路

dp题，可以简单推出 $O(n^2)$ 表达式

注意，因为dp式中出现减法，故设定dp数组的最小值为负无穷
递推式子如下，就分为是否同奇偶

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        dp = std.array(-INF, n)
        
        dp[0] = nums[0]
        res = nums[0]
        for i in range(1, n):
            for j in range(i):
                if (nums[i] % 2) == (nums[j] % 2):
                    dp[i] = std.max(dp[i], dp[j] + nums[i])
                else:
                    dp[i] = std.max(dp[i], dp[j] + nums[i] - x)
            res = std.max(res, dp[i])
        
        return res

但可以观察到第二维可以优化，只需要记录奇数和偶数的目前dp最大值即可，从该处转移即可
（下面的代码的dp[i]其实可以用cur变量去替代，不用开数组的）

代码


'''
Author: NEFU AB-IN
Date: 2024-06-27 11:23:00
FilePath: \LeetCode\2786\2786.py
LastEditTime: 2024-06-27 12:39:12
'''
# import
from functools import cache
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from typing import TypeVar, List, Dict, Any, Union, Generic

TYPE = TypeVar('TYPE')

# Data structure
class SA(Generic[TYPE]):
    def __init__(self, x: TYPE, y: TYPE):
        self.x: TYPE = x
        self.y: TYPE = y

    def __lt__(self, other: 'SA[TYPE]') -> bool:
        return self.x < other.x
    
    def __eq__(self, other: 'SA[TYPE]') -> bool:
        return self.x == other.x and self.y == other.y
    
    def __repr__(self) -> str:
        return f'SA(x={self.x}, y={self.y})'


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))

# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE) -> int:
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)

# —————————————————————Division line ——————————————————————

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        dp = std.array(-INF, n)
        
        dp[0] = nums[0]
        res = nums[0]
        if nums[0] % 2 == 0:
            even_mx, odd_mx = nums[0], -INF
        else:
            even_mx, odd_mx = -INF, nums[0]
            
        for i in range(1, n):
            if nums[i] % 2 == 0:
                dp[i] = std.max(dp[i], even_mx + nums[i])
                dp[i] = std.max(dp[i], odd_mx + nums[i] - x)
                even_mx = std.max(even_mx, dp[i])
            if nums[i] % 2 != 0:
                dp[i] = std.max(dp[i], odd_mx + nums[i])
                dp[i] = std.max(dp[i], even_mx + nums[i] - x)
                odd_mx = std.max(odd_mx, dp[i])

            res = std.max(res, dp[i])
        
        return res


# print(Solution().maxScore([2, 1, 3, 7, 9], 50))
print(Solution().maxScore([85,12], 79))

2786. 访问数组中的位置使分数最大

题意

思路

代码