赞
踩
- s = input().strip()
- dp = [0] * (len(s) + 1)
- dp[1] = ord(s[0]) - 96
- for i in range(2,len(s) + 1):
- dp[i] = max(dp[i - 2] + ord(s[i - 1]) - 96,dp[i - 1])
- print(dp[len(s)])
- #第I题:样例输入第一行为"4 4"
- #二分答案 + 区间合并
- def check(t):#判断t时刻 是否能让管道全部检测到水
- brr = []#每个在t时刻 打开的阀门的左右区间 宽度
- for i in range(n):
- if arr[i][0] > t:break
- Si,Li = arr[i]
- #保持l最小是1 r最大是Len 超过就没有必要判断了
- l,r = max(1,Li - (t - Si)),min(Len,Li + (t - Si))
- brr.append((l,r))
- brr.sort(key=lambda x:x[0])#按左端点排序
- #区间合并
- end = 0
- for l,r in brr:
- if l - end > 1:return False
- end = max(end,r)
- if end == Len:return True
- return end == Len
-
-
-
- def main():
- l,r = 1,Len + arr[-1][0] + 100
- ans = r
- while l <= r:
- mid = (l + r) // 2
- if check(mid):ans = mid;r = mid - 1
- else:l = mid + 1
- return ans
-
-
-
- n,Len = map(int,input().strip().split())
- arr = list()#阀门a[i][0]-什么时刻打开 a[i][1] - 阀门编号
- for i in range(n):
- L,S = map(int,input().strip().split())
- arr.append((S,L))
- arr.sort(key=lambda x:x[0])#按打开时刻排序
- ans = main()
- print(ans)
-

- #贪心 低位 -> 高位 遍历
- #每次衡量当前位 到目标值 所需最小花费
- #进位后,还要判断对进位后数字的影响
- #返回x[u] 一直加1 到与y[u]位相同所需要的花费和加完后有改动的字符串
-
- def count(u,t):
- res = 0
- while u != 0 and t != 0:
-
- c = x[u]
- sub = (c - y[u] + 10) % 10
- jf = (y[u] - c + 10) % 10
- after = min(sub,jf)#进位前需要的最小花费
- c += t
- if c == 10:c = 0;t = 1
- elif c == -1:c = 0;t = -1
- else:t = 0
-
- sub = (c - y[u] + 10) % 10
- jf = (y[u] - c + 10) % 10
- now = min(sub,jf)#进位后需要的最小花费
-
- res += now - after
- u -= 1
- return res
- #加法
- def Sum(u):
- res = y[u] - x[u]
- if res < 0:
- #否则表示要进位
- res = y[u] + 10 - x[u]
- res += count(u - 1,1)
- return res
- #减法
- def Mul(u):
- res = x[u] - y[u]
- if res < 0:
- #否则表示要借位
- res = x[u] + 10 - y[u]
- res += count(u - 1,-1)
- return res
-
-
-
- def main():
- ans = 0#要移动的次数
- r = n - 1
- while r >= 0:
- if x[r] == y[r]:r -= 1;continue
- SumCnt,MulCnt = Sum(r),Mul(r)
- ## print(SumCnt,MulCnt)
- if SumCnt <= MulCnt:#做加法
- ans += (y[r] - x[r] + 10) % 10
- ## print("Sum",r,ans,(y[r] - x[r] + 10) % 10)
- if y[r] < x[r]:#说明进位了
- t,i = 1,r - 1#向前进位
- while i != -1 and t != 0:
- if x[i] == 9:x[i] = 0;t = 1
- else:x[i] += t;t = 0
- i -= 1
-
- else:#做减法
- ans += (x[r] - y[r] + 10) % 10
- ## print("Mul",r,ans,(x[r] - y[r] + 10) % 10)
- if y[r] > x[r]:#要借位
- t,i = -1,r - 1
- while i != -1 and t != 0:
- if x[i] == 0:x[i] = 9;t = -1
- else:x[i] += t;t = 0
- i -= 1
- ## print(x[:r])
- r -= 1
- return ans
-
-
-
- n = int(input().strip())
- x,y = list(map(int,input().strip())),list(map(int,input().strip()))
- ##print(n,x,y)
- ans = main()
- print(ans)

我题意理解错了,我理解成选了第i层后,第i-1和第i+1层都不能选...
- def add(a,b):
- node.append((b,h[a]))
- h[a] = len(node) - 1
-
- def dfs(f,root):
- #要么选
- floot[f].append(root)
- t = h[root]
- while t != -1:
- b,t = node[t]
- dfs(f + 1,b)
-
- def main():
- for i in range(n,0,-1):
- for j in floot[i]:
- dp[i] = max(dp[i],v[j])
- if i + 2 <= n:dp[i] += dp[i + 2]
-
-
- n = int(input().strip())
- node,h = [0],[-1] * (n + 1)#邻接表存储树
- par = list(map(int,input().strip().split()))
- v = list(map(int,('0 ' + input()).strip().split()))
- for i in range(2,n + 1):
- add(par[i - 2],i)
- floot = [[] for i in range(n + 1)]#每一层的结点有哪些
- dfs(1,1)#划分层级
- dp = [0] * (n + 1)
- main()
- ans = dp[1]
- if n >= 2:ans = max(ans,dp[2])
- print(ans)
-
-
-
-

- def add(x,y,z):
- node.append((y,z,h[x]))
- h[x] = len(node) - 1
-
-
- def dijk(start):
- dis[start] = 0
- for i in range(n):
- t = -1
- for j in range(n):
- if st[j]:continue
- if t == -1 or dis[t] > dis[j]:
- t = j
- st[t] = True
- j = h[t]
- while j != -1:
- y,z,j = node[j]
- if st[y]:continue
- if dis[y] == dis[t] + z:
- path[y].append(t)
- elif dis[y] > dis[t] + z:
- dis[y] = dis[t] + z
- path[y] = [t]#只能从t转移
-
-
- def count(x):
- res,st = 0,[False] * (n + 1)
- Que = [x]
- while len(Que) != 0:
- t = Que.pop()
- if st[t]:continue
- for i in path[t]:
- if i == 1:
- res += 1
- st[t] = True
- else:
- Que.append(i)
- return res
-
-
- n,m = map(int,input().strip().split())
- node,h = [0],[-1] * (n + 1)
- for i in range(m):
- x,y,z = map(int,input().strip().split())
- add(x,y,z)
- add(y,x,z)
- dis,st = [float('inf')] * (n + 1),[False] * (n + 1)
- path = [[] for i in range(n + 1)]#i从哪个最短路过来的
- dijk(1)
- path[1] = [1]#1默认是从自己过来的
- for i in range(1,n + 1):
- if dis[i] == float('inf'):print(-1)
- else:print(count(i) - 1)

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。