#include <iostream> #include <cstring> #include <algorithm> const int MAX_B = 1005; const int MAX_TIMES = 1000005; int arrayB[MAX_B]; int arrayC[MAX_B]; int times[MAX_TIMES]; int dp[MAX_TIMES]; void calculateTimes(int x, int step) { if (x > MAX_B) return; if (times[x] != 1919810 && step >= times[x]) return; if (step < times[x]) times[x] = step; for (int i = 1; i <= x; i++) calculateTimes(x + x / i, step + 1); } int calculateMoney(int n, int k, int b[], int c[], int sum) { int ans = 0; int maxSteps = 0; memset(dp, 0, sizeof dp); for (int i = 1; i <= n; i++) { maxSteps = std::max(maxSteps, times[b[i]]); ans += times[b[i]]; } if (k >= maxSteps * n || k >= ans) { return sum; } for (int i = 1; i <= n; i++) { for (int j = k; j >= times[b[i]]; j--) { dp[j] = std::max(dp[j], dp[j - times[b[i]]] + c[i]); } } return dp[k]; } int main() { for (int i = 1; i < MAX_B; i++) { times[i] = 1919810; } calculateTimes(1, 0); int t; std::scanf("%d", &t); for (int i = 1; i <= t; i++) { int sum = 0; int n, k; std::scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) { std::scanf("%d", &arrayB[i]); } for (int i = 1; i <= n; i++) { std::scanf("%d", &arrayC[i]); sum += arrayC[i]; } std::printf("%d\n", calculateMoney(n, k, arrayB, arrayC, sum)); } return 0; }

以下是将该代码转换为 Python 语言的版本：

import sys
MAX_B = 1005
MAX_TIMES = 1000005
arrayB = [0] * MAX_B
arrayC = [0] * MAX_B
times = [1919810] * MAX_B
dp = [0] * MAX_TIMES

def calculateTimes(x, step):
    if x > MAX_B:
        return
    if times[x] != 1919810 and step >= times[x]:
        return
    if step < times[x]:
        times[x] = step
    for i in range(1, x+1):
        calculateTimes(x + x // i, step + 1)

def calculateMoney(n, k, b, c, sum):
    ans = 0
    maxSteps = 0
    dp = [0] * MAX_TIMES
    for i in range(1, n+1):
        maxSteps = max(maxSteps, times[b[i]])
        ans += times[b[i]]
    if k >= maxSteps * n or k >= ans:
        return sum
    for i in range(1, n+1):
        for j in range(k, times[b[i]]-1, -1):
            dp[j] = max(dp[j], dp[j - times[b[i]]] + c[i])
    return dp[k]

if __name__ == '__main__':
    for i in range(1, MAX_B):
        times[i] = 1919810
    calculateTimes(1, 0)
    t = int(input())
    for i in range(t):
        sum = 0
        n, k = map(int, input().split())
        arrayB = list(map(int, input().split()))
        arrayC = list(map(int, input().split()))
        sum = sum(arrayC)
        print(calculateMoney(n, k, arrayB, arrayC, sum))