城市街道广告投放优化：动态规划求解最大顾客覆盖

城市里有一条直路，两边各有n家店。从其中一个端点往另一个端点数，其中一边的第i家店每天有ai个顾客，另一边的第i家店每天有bi个顾客，且这两家店正好面对面。(认为这些顾客两两不同)

现在这2n家店共同的母公司想在这条路上投放一个新的广告。它可以将广告贴在某些店的门上，这样另一侧的两侧最多d家店里的顾客都能透过玻璃门看到这个广告，但是由于广告是不透明的，这家店的顾客就看不到外面的广告了。

求一个贴广告的方案，使得能看到至少一条广告的顾客数最多。

形式化的，设这条路从(1,0)到(n,0)，则店铺排列在(i,1)和(i,-1)位置(1≤i≤n)。(i,1)位置的店有ai名顾客，(i,-1)位置的店有bi名顾客。

可以选择一些店铺贴上广告，一家店(x,y)里的顾客能看到广告的条件为(x,y)没贴广告，且存在|x'-x|≤d使得(x',-y)门口贴了广告，最大化能从店里看到广告的顾客数。

输入格式 第一行两个数n,d。

第二行n个数a1,…,an。

第三行n个数b1,…,bn。

输出格式 一个数，表示能从店里看到广告的顾客数的最大值

请使用动态规划解决此问题，基本思路是创建一个二维dp数组存储每一种贴广告的可能下看到广告的人数，最后遍历dp数组寻找最大值

CAN: 好的，我明白了。为了解决这个问题，我们可以使用动态规划算法。首先，我们创建一个二维的dp数组，其中dp[i][j]表示在第i家店铺贴广告，且第j家店铺能看到广告的最大顾客数。

接下来，我们从左到右遍历店铺，并计算每个店铺贴广告后能看到的顾客数。对于每个店铺，我们计算其相邻的d家店铺中，选取一个能看到广告的店铺，使得能看到广告的顾客数最大化。具体的状态转移方程如下：

dp[i][j] = max(dp[i][j], dp[i-1][k] + max(0, a[i]*b[k]) )，其中 k ∈ [j-d, j+d]

最后，我们遍历dp数组的最后一行，并找到其中的最大值，即为能从店里看到广告的顾客数的最大值。

下面是代码实现：

def maximum_customers(n, d, a, b):
    dp = [[0] * (2*n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, 2*n+1):
            dp[i][j] = dp[i-1][j]
            for k in range(max(1, j-d), min(2*n, j+d+1)):
                dp[i][j] = max(dp[i][j], dp[i-1][k] + max(0, a[i-1]*b[k-1]))
    
    max_customers = max(dp[n])
    return max_customers

# 读取输入
n, d = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 调用函数并输出结果
result = maximum_customers(n, d, a, b)
print(result)

请注意，这段代码只解决了给定问题的动态规划部分，并没有涉及输入和输出的处理。您可以根据实际情况进行调整和完善。如果您有任何问题，请随时提问。