# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param inorder int整型一维数组 中序遍历序列 # @param postorder int整型一维数组 后序遍历序列 # @return TreeNode类 # class Solution: def buildTree(sel...

# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 the root of binary tree # @return int整型二维数组 # class Solution: def threeOrders(self , root: TreeNode) ...

import sys # 对于一个最大和的子矩阵来说，多加上下左右任意一行或着一列，该行和列的和都为0 # 固定矩阵的最上行和最下行，相当于遍历每一列使得连续几列的最大 # 假设该列是 dp[i], dp[i] = max(sum(i列),dp[i-1]+ sum(i列)) # sum[i]列这个可以通过求前缀和获得 n = int(input()) col_sum = [[0]*n for _ in range(n)] arr = [] for i in range(n): data = input().strip().split(' ') data = [v for ...

import sys # 每天都有 2k个状态，即第一次买入， 第一次卖出 # 用 buy 和 sell 来累计之前k次买入卖出的钱 # sell[k] 为第k卖出最大收益， buy[k]为第k次买入最大收益 # sell[k] = max(buy[k-1] + prices[i], sell[k]) # buy[k] = max(sell[k-1]-prices[i], buy[j]) n, k = list(map(int,input().strip().split(' '))) prices = list(map(int,input().strip().split(' ')...

import sys # 卖出之前没法买入， # 假设第一次卖出是在第i天 # 那么就是寻找 0～i天 和i到n天两段时间内的最大收益 # 因此两个动态规划 # dp1 从 0到 i 表示 到第i天的最大收益 # dp2 从 i到n 表示 i~n天的最大收益 n = int(input()) if n <= 1: print(0) else: prices = list(map(int,input().strip().split(' '))) dp1 = [0] * n dp2 = [0] * n pre_min = prices[0] ...

import sys # 对于每天来说，每天可能有三种可操作状态，可买入，可卖出，和不操作三种选择 # 假设当天可买入状态下,从第一台呢到第i天能收获的最高利润是 buy[i] # 当天可卖出状态下能收获的最高利润是 sell[i] # 不操作的话收益和 0~i之间某一天的买入或者卖出一样，无需专门记录 # 因此 # buy[i] = max(sell[i-1] - prices[i], buy[i-1]) # sell[i] = max(buy[i-1] + prices[i], sell[i-1] # 最后能max(buy[i],sell[i]) 即可 n = int(input())...

import sys # dp[i]为第i天卖出可获得的最高收益 # dp[i] = prices[i] - pre_min (之前天里面的最低值) # 最后输出max[dp] n = int(input()) if n<=1: print(0) else: dp = [0] * (n+1) dp[0] = 10**5 + 5 pre_min = dp[0] prices = list(map(int,input().strip().split(' '))) for i in range(1,n+1): dp[i] ...

import sys # 下一个要跳跃的点，是在当前能跳跃的点里面，能跳最远的 # 因为其他点的话，当前能跳跃的点能到达其他所有点能跳跃的地方 n = int(input()) if n==0: print(-1) elif n == 1: print(0) else: nums = list(map(int,input().strip().split(' '))) boundary = nums[0] max_len = nums[0] time = 0 next_boundary = nums[0] for i in...

from sre_compile import BRANCH import sys # 17:57 # 方法一 :dp[i] 为 到 i的最大积分, O(MN), 超时 # dp[i] = max(j从0到i-1过程中，满足nums[i] > i-j，dp[j]+nums[i]) n = int(input()) if n == 0: print(-1) else: # flag = True # nums = list(map(int,input().strip().split())) # dp = [0]* n # for i in ...

import sys # 方法一： O(NN)，超时 # dp[i] = 能否跳到i # dp[i] = (j从0~i-1, dp[j]==1 & nums[j]>= (i-j)) n = int(input()) nums = list(map(int, input().strip().split())) # dp = [False] * (n) # dp[0] = True # for i in range(1,n): # for j in range(i): # if dp[j] and nums[j] >= (i-j): # ...

import sys # dp[n] 为 0～n 的最大不相邻和 # dp[n] = max(dp[n-2]+a_n, dp[n-1]) n = int(input()) nums = list(map(int,input().strip().split())) dp = [0] * (n+2) # 因为要提前看到前两位的数 for i in range(2,n+2): dp[i] = max(dp[i-2]+nums[i-2], dp[i-1]) print(dp[-1])

import sys # dp[i][j] 为 从 i 到 j 的最长子序列 # dp[i][j] = max(dp[i+1][j-1] + 2*(s[i]==s[j]),dp[i][j-1], dp[i+1][j]) # 需要知道 dp[i+1][j-1]和dp[i][j-1]的值，说明填表方向是,第一维从n到i，第二维从0到j # 这种填表方向可行 s = input().strip() n = len(s) dp = [[0]*n for _ in range(n)] for i in range(n): dp[i][i] = 1 for i in range(n-1...

import sys # 峰形队列其实是求 0~i的最长严格上升子序列 + i+1 ~0的最长严格下降子序列 # 求最少出列，就是求它俩相加最大 n = int(input()) height = list(map(int,input().strip().split())) dp1 = [0] * n # dp[i]记录从0到i的最长上升序列 dp2 = [0] * n # dp2[i]记录从i到n的最长下降序列，或者从n到i的最长上升序列 dp1[0], dp2[n-1] = 1, 1 for i in range(1,n): max_num = 0 for j i...