头像

SeiunSky




离线:6天前


最近来访(38)
用户头像
bobo0612
用户头像
ZacharyG
用户头像
今天也是刷题的一天
用户头像
Carson_cyc
用户头像
qiao
用户头像
dushucheng0901
用户头像
test001
用户头像
Fool_vamp
用户头像
nosajuil
用户头像
妮妮姆
用户头像
114514a
用户头像
Whalefall.
用户头像
花开城南与君在
用户头像
Marky
用户头像
学不会我就死
用户头像
shibaguji


n = int(input())
t = list(map(int, input().split()))
a = [0]
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

m = 0
for i in range(n):
    if a[m] != t[i]:
        m += 1
        a.append(t[i])

for len in range(2, m + 1):
    for i in range(1, m - len + 2):
        j = i + len - 1
        if a[i] == a[j]:
            dp[i][j] = dp[i + 1][j - 1] + 1
        else:
            dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1

print(dp[1][m])



什么是前后缀分解?
通常来说,对于区间[1, n], 前缀和分解就是枚举一个区间中的一个点i, 使得从i划分的两个区间可以分开讨论
对于前一个区间采用从前向后的方法,对于后一个区间采用从后向前的方法

本题将区间从i断开,用f记录左区间在i处断开的连续序列最大值(包含a[i]), 用g记录右区间在i处断开的连续序列最大值(包含a[i])

Py3 代码

T = int(input())

for _ in range(T):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    f = [-float('inf')] * (n + 2)
    g = [-float('inf')] * (n + 2)

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

    s = 0
    for j in range(n, 0, -1):
        s = max(0, s) + a[j]
        g[j] = max(g[j + 1], s)

    res = -float('inf')
    for i in range(1, n + 1):
        res = max(res, f[i] + g[i + 1])

    print(res)




T = int(input())

for _ in range(T):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    f = [-float('inf')] * (n + 2)
    g = [-float('inf')] * (n + 2)

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

    s = 0
    for j in range(n, 0, -1):
        s = max(0, s) + a[j]
        g[j] = max(g[j + 1], s)

    res = -float('inf')
    for i in range(1, n + 1):
        res = max(res, f[i] + g[i + 1])

    print(res)



SeiunSky
11天前
N = 1e9
n = int(input())
a = [2 ** i for i in range(int(math.log(n, 2)) + 1)]
f = [0] * (n + 1)
f[0] = 1

for i in range(len(a)):
    for j in range(a[i], n + 1):
        f[j] = int((f[j] + f[j - a[i]]) % N)

print(f[n])



SeiunSky
11天前

py3 代码

N = 1e9
n = int(input())
a = [2 ** i for i in range(int(math.log(n, 2)) + 1)]
f = [0] * (n + 1)
f[0] = 1

for i in range(len(a)):
    for j in range(a[i], n + 1):
        f[j] = int((f[j] + f[j - a[i]]) % N)

print(f[n])



SeiunSky
11天前
N, V = map(int, input().split())
v = [[0] for _ in range(N + 1)]
w = [[0] for _ in range(N + 1)]
s = [0] * (N + 1)
f = [[0 for _ in range(V + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    si = int(input())
    s[i] = si
    for _ in range(si):
        vi, wi = map(int, input().split())
        v[i].append(vi)
        w[i].append(wi)

for i in range(1, N + 1):
    for j in range(V + 1):
        for k in range(s[i] + 1):
            if j >= v[i][k]:
                f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k])

print(f[N][V])



SeiunSky
11天前
N, V = map(int, input().split())
v = [0] * (N + 1)
w = [0] * (N + 1)
f = [0] * (V + 1)

for i in range(1, N + 1):
    vi, wi = map(int, input().split())
    v[i] = vi
    w[i] = wi

for i in range(1, N + 1):
    for j in range(v[i], V + 1):
        f[j] = max(f[j], f[j - v[i]] + w[i])

print(f[V])



SeiunSky
11天前
N, V = map(int, input().split())
f = [0] * (V + 1)
v = [0]
w = [0]

for _ in range(1, N + 1):
    vi, wi = map(int, input().split())
    v.append(vi)
    w.append(wi)

for i in range(1, N + 1):
    for j in range(V, v[i] - 1, -1):
        f[j] = max(f[j], f[j - v[i]] + w[i])

print(f[V])



SeiunSky
12天前
T = int(input())

for _ in range(T):
    n, k = map(int, input().split())
    if k % 3 != 0:
        print("Alice") if n % 3 != 0 else print("Bob")
    else:
        n = n % (k + 1)
        print("Alice") if n == k or n % 3 != 0 else print("Bob")



SeiunSky
13天前

一道利用隔板法的题,先将这n个数分为k + 1组,一共有n - 1个位置可以放置隔板,可分组C[n - 1][k]。组内选中的水果相同,与左侧相邻组的水果种类不同。第一组因为在最左边没有限制所以可以选择m种,第二组因为左边有一组,若不同则只有(m - 1)种可能,第三组直到最后一组都与第二组相同

Py3 代码

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


def qmi(x, u):
    res = 1
    while u:
        if u & 1:
            res = (res * x) % N
        x = (x * x) % N
        u >>= 1
    return res


for i in range(n):
    for j in range(i + 1):
        if j <= k:
            if not j:
                f[i][j] = 1
            else:
                f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % N


print((m * qmi(m - 1, k) * f[n - 1][k]) % N)