1, 签到
2,动态规划
2,动态规划
n = int(input()) string = input() dp = [[0]*2 for x in range(n)] dp[0][0] = 1 dp[0][1] = float("inf") for x in range(1, n): dp[x][0] = dp[x-1][0]+1 midIndex = (x+1)//2 if (x+1)%2==0 and string[:midIndex]==string[midIndex:x+1]: dp[x][1] = min(dp[x-1][1]+1, dp[midIndex-1][0]+1) else: dp[x][1] = dp[x-1][1]+1 print(min(dp[n-1]))3,还是动态规划
T = int(input()) for x in range(T): n, m, k = list(map(int, input().split())) prohibitColorBit = [] #注意ci 1<=ci<=m for x in range(m): line = set(map(lambda x:int(x)-1, input().split())) bit = 0 for x in line: bit = bit | (1<<x) prohibitColorBit.append(bit) #0<=ci<m dp = [[0]*m for x in range(n)] for x in range(n): for curColor in range(m): if x==0: dp[x][curColor] = 1 continue else: for prevColor in range(m): if 1<<curColor & prohibitColorBit[prevColor]: continue else: dp[x][curColor] += (dp[x-1][prevColor]) print(sum(dp[n-1])%(10**9+7))4,还是动态规划( 只a了60%)
n = int(input()) ai = list(map(int, input().split())) bi = list(map(int, input().split())) dp = [[0]*2*n for x in range(2*n)] preSum = [0] for x in range(len(ai)): curSum = -ai[x] + bi[x] curSum += preSum[-1] preSum.append(curSum) for x in range(2*n-1, -1, -1): for y in range(2*n): if x==y: dp[x][y] = ai[x] elif y<x: continue else: #dp[x][y]表示干掉x到y需要的最少血量 #dp[x+1][y] #干掉x, y-1剩下的血量 leftLeft = dp[x][y-1] + preSum[y]-preSum[x] rightLeft = dp[x+1][y] + preSum[y+1] - preSum[x+1] leftNeed = dp[x][y-1] rightNeed = dp[x+1][y] if leftLeft <= ai[y]: leftNeed += (ai[y]-leftLeft+1) if rightLeft<= ai[x]: rightNeed += (ai[x]-rightLeft+1) #处于同一边 if x<=n-1 and y<=n-1: # print(y) dp[x][y] = leftNeed continue if x>=n and y>=n: # print(x) dp[x][y] = rightNeed continue if leftNeed<rightNeed: # print(y) dp[x][y] = leftNeed else: # print(x) dp[x][y] = rightNeed print(dp[0][2*n-1]) # 3 # 5 6 7 8 9 5 # 8 7 5 6 10 12感觉是由于最后的时候可以人怪都死完,(我是让所有时候人都不能死)
全部评论
(3) 回帖