2034

Lampropeltis
yxc的小迷妹
Mappel

Capoo-Capoo
Eureka_24

xiaozd
NUC-CYJ
zst_2001

.Zero

Suimou

ck1000
xjtu_zfw

题目描述

Hello Kitty想摘点花生送给她喜欢的米老鼠。

Hello Kitty只能向东或向南走，不能向西或向北走。

输入样例

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5


输出样例

8
16


题目分析

动态规划 $O(n^2)$

$(i, j)$从$(i-1, j)$即上方过来
$(i, j)$从$(i, j-1)$即左方过来

DP问题注意初始化:这里左上角的点的状态值应该初始化为这个点的花生数量
f[1][1] = w[1][1]
---------------------------------------------------------------------------------------------------------------------

tips:1 算法中的坐标系一般如下图所示，与数学意义上的坐标系存在区别

2.二维数组这里暂时我只会分开来按行读入

Py 代码

import sys

N = 110
w = [[0] * N for i in range(N)]
f = [[0] * N for i in range(N)]

t = int(input())
for i in range(t):
n, m = map(int, input().split())
for i in range(1, n + 1):
ls = list(map(int, input().split()))
for j in range(1, m + 1):
w[i][j] = ls[j - 1]

f[1][1] = w[1][1]
for i in range(1, n + 1):
for j in range(1, m + 1):
if i == 1:
f[i][j] = f[i][j - 1] + w[i][j]
elif j == 1:
f[i][j] = f[i -1][j] + w[i][j]
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]

print(f[n][m])



import sys

N = 3010
f = [[0] * N for i in range(N)]

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

for i in range(1, n + 1):
maxv = 1
for j in range(1, n + 1):
f[i][j] = f[i - 1][j]
if a[i] == b[j]:
f[i][j] = max(f[i][j], maxv)
if b[j] < a[i]:
maxv = max(maxv, f[i - 1][j] + 1)

print(max(f[n][:]))


import sys

N = 55
up = [0] * N
down = [0] * N

def dfs(u, su, sd):
global ans
if su + sd >= ans:
return
if u == n:
ans = min(ans, su + sd)
return

l = 0; r = su
while l < r:
mid = l + r >> 1
if up[mid] > h[u]:
r = mid
else:
l = mid + 1

if l == su:
t1 = up[su]
up[su] = h[u]
dfs(u + 1, su + 1, sd)

up[su] = t1
else:
t2 = up[l]
up[l] = h[u]
dfs(u + 1, su, sd)

up[l] = t2

l = 0; r = sd
while l < r:
mid = l + r >> 1
if down[mid] < h[u]:
r = mid
else:
l = mid + 1

if l == sd:
t3 = down[su]
down[sd] = h[u]
dfs(u + 1, su, sd + 1)

down[sd] = t3
else:
t4 = down[l]
down[l] = h[u]
dfs(u + 1, su, sd)

down[l] = t4

while True:
n = int(input())
if n == 0:
break
else:
h = list(map(int, input().split()))

ans = n

dfs(0, 0, 0)

print(ans)



import sys

N = 1010
f = [1] * N
q = [0] * N
h = list(map(int, input().split()))

len_h = len(h)

for i in range(len_h):
for j in range(i):
if h[i] <= h[j]: # 这里导弹是不下降的，所以要等号
f[i] = max(f[i], f[j] + 1)
print(max(f))

cnt = 0 # cnt代表导弹系统数量
for i in range(len_h):
k = 0 # k代表第i发应该被接在哪一个系统后面
while k < cnt and q[k] < h[i]:
k += 1
if k == cnt:
q[cnt] = h[i]
cnt += 1
else:
q[k] = h[i]

print(cnt)


输出格式

样例 #1

样例输入 #1

4 3
513 598 567 689
500 600 550


样例输出 #1

32


题目分析：

二分：

$check$函数的返回值为$True$的情况：a[i] <= target，此时处于左区间内，l = mid

C++ 代码

import sys

n, m = map(int, input().split())

a = list(map(int, input().split()))
a.sort()
res = 0
b = list(map(int, input().split()))
for i in range(m):
x = b[i]
l = 0; r = n - 1
while l < r:
mid = l + r + 1>> 1
if a[mid] <= x:
l = mid
else:
r = mid - 1
s1 = a[l]
if s1 == x:
continue
elif l + 1 < n:
s2 = a[l + 1]
res += min(abs(s2 - x), abs(s1 - x))
else:
res += abs(s1 - x)

print(res)


输出格式

样例 #1

样例输入 #1

25 5 2
2
11
14
17
21


样例输出 #1

4


题目分析：

二分

py 代码

import sys

N = 50010
a = [0] * N

def check(x):
s = 0 # 需要挪走的石头总量
now = 0 # 目前石头位置
next_ = 0 #下一块石头的位置
while next_ < n + 1:
next_ += 1
if a[next_] - a[now] < x:
s += 1
else:
now = next_
if s > m:
return False
else:
return True

### 跳石头
d, n, m = map(int, input().split())

a[n + 1] = d
for i in range(1, n + 1):
x = int(input())
a[i] = x

l = 1; r = d
while l < r:
mid = l + r + 1 >> 1
if check(mid):
l = mid
else:
r = mid - 1
print(l)



输出格式

样例 #1

样例输入 #1

3 7
232
124
456


样例输出 #1

114


分析过程

二分

py 代码

import sys

def check(x):
res = 0
for i in range(n):
res += a[i] // x
return res

n, k = map(int, input().split())
a = []
for i in range(n):
x = int(input())
a.append(x)
a.sort()
res = 0

if k > sum(a):
print(0)
else:
l = 1; r = a[n - 1]
while l < r:
mid = l + r + 1 >> 1
if check(mid) >= k:
l = mid
else:
r = mid - 1
print(l)



输出格式

样例 #1

样例输入 #1

4 1
1 1 2 3


样例输出 #1

3


思路：

时间复杂度：二分 $O(n\log n)$

1. 求起始下标：
将列表分为左右两个区间，左区间是小于目标元素，右区间是大于等于目标元素。
因此是求右区间的左边界，套用第二个模板
$check$函数的$True$应该对应r = mid, $False$应该对应l = mid + 1
2. 求末尾下标：
将列表分为左右两个区间，左区间是小于等于目标元素，右区间是大于目标元素。
因此是求左区间的右边界，套用第一个模板
$check$函数的$True$应该对应l = mid,$False$应该对应r = mid - 1

py 代码

import sys

n, c = map(int, input().split())

def chek(q):
l = 1; r = n; res = 0
while l < r:
mid = l + r >> 1
if a[mid] >= q:
r = mid
else:
l = mid + 1
left = l
if a[l] != q:
return 0
else:
l = 1; r = n
while l < r:
mid = l + r + 1 >> 1
if a[mid] <= q:
l = mid
else:
r = mid - 1
right = l
if left == right:
res += 1
else:
res += right - left + 1
return res

a = [-10] + list(map(int, input().split()))
a.sort()
res = 0
max_ = a[n]
for i in range(1, n + 1):
q = a[i] + c
if q > max_:
continue
else:
res += chek(q)

print(res)



输出格式

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6


样例输出 #1

1 2 -1


分析过程：

二分

py 代码

import sys

n, m = map(int, input().split())

a = [0] + list(map(int, input().split()))
b = list(map(int, input().split()))

for i in range(m):
q = b[i]
l = 1; r = n
while l < r:
mid = l + r >> 1
if a[mid] >= q:
r = mid
else:
l = mid + 1
if a[l] != q:
print(-1, end = " ")
else:
print(l, end = " ")


1. 情况一（求左区间的右边界）
当check函数成立的时候，此时mid处于红色区间（左区间），mid满足check，所以直接l = mid
当check函数不成立的时候，mid处于绿色区间（右区间），此时mid不满足check函数，所以需要减1向左侧靠拢r = mid - 1
注意：这种情况的mid需要加一，mid = l + r + 1 >> 1
代码：
mid = l + r + 1 >> 1
while l < r:
if check():
l = mid
else:
r = mid - 1


1. 情况二（求右区间的左边界）
当check函数成立的时候，此时mid处于绿色区间（右区间），mid满足check，所以直接r = mid
当check函数不成立的时候，mid处于红色区间（左区间），此时mid不满足check函数，所以需要加1向右侧靠拢l = mid + 1
代码：
mid = l + r >> 1
while l < r:
if check():
r = mid
else:
l = mid + 1