头像

王乐


访客:3473

离线:3个月前



王乐
5个月前

题目要点

这个题目除了 DP 外,还可以用贪心解法,比较好理解。
1. 因为我们有无限次的交易次数,那么凡是存在data[i] > data[i-1]情形时,我们就可以获得利润。
2. 利润最大,就是得到所有可能的利润。


算法1

(贪心) $O(n)$

直接捕获序列中所有上升部分(红色)加和即可
截屏2019-12-1415.19.38.png

Python 代码

"""
AcWing 1055. 股票买卖 II
"""
N = 100010

n = int(input())
data = [int(d) for d in input().split()]

profit = 0

for i in range(1, n):
    if data[i] > data[i - 1]:
        profit += (data[i] - data[i - 1])

print(profit)




王乐
5个月前

题目要点

这个题目的前置题目是 1054 ,即仅进行一次交易,如何保证利润最大,我们使用了递推来求解。
两次交易,对于任意点i,划分左半边利润最大(pre)和右半边利润最大(post),然后相加就是两次交易。
思路有点类似于 482 的合唱队形题目。


算法1

(DP) $O(n)$

一次正向 DP + 一次反向 DP

Python 代码

"""
AcWing 1056. 股票买卖 III
"""
N = 100010
pre, post = [0] * N, [0] * N

n = int(input())
data =[int(d) for d in input().split()]

idx = 0
for i in range(n):
    pre[i] = max(pre[i - 1], data[i] - data[idx])
    if data[i] < data[idx]:
        idx = i

idx = n - 1
for i in range(n - 1, -1, -1):
    post[i] = max(post[i + 1], data[idx] - data[i])
    if data[i] > data[idx]:
        idx = i

res = 0
for i in range(n):
    res = max(res, pre[i] + post[i])
print(res)



王乐
5个月前

题目要点

  1. 题目要求对于数$x$,它的约数和$y$小于它本身才就可以连边。我们可以利用这个性质把这道题目转化为1072(求树中最长路径):一个数$y$可以作为多个数$[x_1,x_2,x_3,…]$的约数和,且满足上面的性质。因此我们可以把题目给定的$n$个数转化为一棵树,以 1 作为根节点。
  2. 同时,这个题目中的可以不用邻接表来表示图,因为一个节点的根节点就是他的约数和,直接访问数组即可。
  3. 最后,需要提前处理好$1-n$各个数字的约数和。

算法1

(DP) $O(n)$

从叶子节点开始处理,在处理到(满足条件的)约数和$y$时,找到它的所有子节点,记录子节点路径的最大(m1)和次大值(m2),即可构成路径。

"""
AcWing 1075. 数字转换
"""
N = 50010
m1, m2 = [0] * N, [0] * N
count = [1] * N # 约数和


def solution():
    n = int(input())

    # 约数和处理
    for i in range(2, n // 2 + 1):
        for j in range(2 * i, n + 1, i):
            count[j] += i

    # DP
    for i in range(n, 1, -1):
        if i > count[i]:
            if m1[i] + 1 > m1[count[i]]:
                m2[count[i]] = m1[count[i]]
                m1[count[i]] = m1[i] + 1
            elif m1[i] + 1 > m2[count[i]]:
                m2[count[i]] = m1[i] + 1

    res = 0
    for i in range(1, n + 1):
        res = max(res, (m1[i] + m2[i]))

    print(res)


if __name__ == '__main__':
    solution()





王乐
5个月前

题目要点

这道题目的基本思路就是:枚举所有点的到其余点的距离最大值。但难点在于集合怎么划分,要把一个点的所有可能结果划分为向上(走根节点)走和向下(走子节点)走两类,保证不重不漏。
也就是说我们需要分别结算向上和向下的最大值,取 max 然后再取 min 。
1. 对于向下走,非常简单,直接用 1072 的方法递归遍历子节点即可,不做赘述。
2. 对于向上走,可以把它等效的转换为向下走的问题。

主要说一下怎么转换,直接看下面的图。

截屏2019-12-0722.03.01.png
假设我们想求结点$v$的向上的路径最大值,需要比较$v$到$u$后向下(红色)和向上(绿色)这两类路类。对于绿色路径,由于是相同问题,可以直接递归求解;而为了保证红色的最大则要分情况讨论:

  1. $v$不是$u$的向下最大路径上的点,经过$u$后直接去找$u$ 向下的 的最大路径(保证是红色中的最大)。
  2. $v$是$u$的向下最大路径上的点,如果这时候直接找$u$ 向下的最大(图中为$u,v,w$),就会发现这个路径根本不会向上走,所以需要记录一个次大的路径来保证向上走。

算法1

(DP + DFS)

这里分别用 updown 来表示向上和向下的最大; back 用来表示向下的第二大;由于我们需要知道$v$是否在$u$的最大路径下,所有需要存下每个节点向下最大路径的下一个节点( path)

Python 代码

"""
AcWing 1073. 树的中心
"""


N, INF = 20010, 10000010
e, w, ne, h = [0] * N, [0] * N, [-1] * N, [-1] * N
up, down = [0] * N, [0] * N
back, path = [0] * N, [0] * N

idx = 0


def add_edge(x, y, z):
    global idx
    e[idx] = y
    w[idx] = z
    ne[idx] = h[x]
    h[x] = idx
    idx += 1


def dfs_down(u, root):
    down[u], back[u] = -INF, -INF
    i = h[u]
    while i != -1:
        j = e[i]
        k = w[i]
        i = ne[i]
        if j == root:
            continue
        d = dfs_down(j, u) + k
        if d >= down[u]:
            back[u] = down[u]
            down[u] = d
            path[u] = j
        elif d >= back[u]:
            back[u] = d

    if down[u] == -INF:
        down[u], back[u] = 0, 0
    return down[u]


def dfs_up(u, root):
    i = h[u]
    while i != -1:
        j = e[i]
        k = w[i]
        i = ne[i]
        if j == root:
            continue
        if path[u] == j:
            up[j] = max(up[u], back[u]) + k
        else:
            up[j] = max(up[u], down[u]) + k
        dfs_up(j, u)


def solution():
    n = int(input())
    for i in range(n - 1):
        x, y, z = map(int, input().split())
        add_edge(x, y, z)
        add_edge(y, x, z)

    dfs_down(1, -1)
    dfs_up(1, -1)

    res = INF
    for i in range(1, n + 1):
        res = min(res, max(up[i], down[i]))

    print(res)


if __name__ == '__main__':
    solution()



活动打卡代码 AcWing 905. 区间选点

王乐
6个月前
"""
AcWing 905. 区间选点
"""
N = 100010

sec = []


def solution():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        sec.append([a, b])
    sec.sort(key=lambda x: x[1])

    cnt = 0

    for se in sec:
        l, r = se
        if not cnt or t < l:
            t = r
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    solution()




王乐
6个月前

要注意的点

这里有三个要注意的点:
1. count 函数内位数循环从not x开始:如果 x 为 0,则从第 1 位开始(因为首位不能是 0),否则从 0 开始
2. 因为 python 的原因,省掉了 num 函数,使用字符串切片转 int 来替代。但是,需要先对切片做一个判断,检查是否为空。
3. 即使为空,在 seq[i]==x 等于时那个 1 仍然要加(可以想一下 10 第 1 位里面找 0 的操作)


Python 代码

def count(n, x):
    if not n:
        return 0
    cnt = 0
    seq = str(n)
    l = len(seq)

    for i in range(not x, l):
        if i:
            cnt += (int(seq[:i])) * pow(10, l - i - 1)
            if not x:
                cnt -= pow(10, l - i - 1)

        if int(seq[i]) == x:
            if seq[i + 1:]:
                cnt += int(seq[i + 1:])
            cnt += 1
        elif int(seq[i]) > x:
            cnt += pow(10, l - i - 1)
    return cnt


def solution():
    while 1:
        a, b = map(int, input().split())
        if a == b == 0:
            break
        res = []
        for i in range(0, 10):
            if a > b:
                a, b = b, a
            res.append(count(b, i) - count(a - 1, i))
        print(' '.join(map(str, res)))


if __name__ == '__main__':
    solution()



王乐
6个月前
"""
AcWing 897. 最长公共子序列
"""

N = 1010

n, m = map(int, input().split())
f = [[0] * N for _ in range(N)]


def solution():
    a = ' ' + input()
    b = ' ' + input()

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

    print(f[n][m])


if __name__ == '__main__':
    solution()




王乐
6个月前
"""
AcWing 896. 最长上升子序列 II
"""


N = 100010

n = int(input())
f = [0 for _ in range(N)]
idx = 1


def solution():
    global idx
    w = [int(d) for d in input().split()]
    w = [-2e9] + w
    f[1] = w[1]

    for i in range(2, n + 1):
        l, r = 0, idx
        while l < r:
            mid = l + r + 1 >> 1
            if f[mid] < w[i]:
                l = mid
            else:
                r = mid - 1
        idx = max(idx, l + 1)
        f[l + 1] = w[i]

    print(idx)


if __name__ == '__main__':
    solution()



活动打卡代码 AcWing 899. 编辑距离

王乐
6个月前
"""
AcWing 902. 最短编辑距离
"""
N = 1010

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


def solution():
    n = int(input())
    a = ' ' + input()
    m = int(input())
    b = ' ' + input()

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 1)
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]))

    print(f[n][m])


if __name__ == '__main__':
    solution()




王乐
6个月前
N = 100010

n = int(input())
f = [1 for _ in range(N)]


def solution():
    w = [int(d) for d in input().split()]
    w = [0] + w
    for i in range(2, n + 1):
        for j in range(1, i):
            if w[j] < w[i]:
                f[i] = max(f[i], f[j] + 1)

    res = 0
    for i in range(1, n + 1):
        res = max(res, f[i])

    print(res)

if __name__ == '__main__':
    solution()