思路:和算法基础课《石子合并》一样,不过要判断颜色是否相同
(1)f[i][j]
:表示区间[i,j]所有合并方案中总花费的最小值,初始化为正无穷;
(2)g[i][j]
:表示区间[i, j]的颜色,也就是这堆石子的颜色
(3)关键一步:判断能否合并,合并后如何更新颜色,下面代码(g[i][k] + 1) % 3
也可以换成(g[k + 1][j] + 1) % 3
if g[i][k] == g[k + 1][j]: # 如果两堆石子颜色相同,g[i][j]表示区间[i, j]的颜色
if f[i][j] > f[i][k] + f[k + 1][j] + w[j] - w[i - 1]:
f[i][j] = f[i][k] + f[k + 1][j] + w[j] - w[i - 1]
g[i][j] = ((g[i][k] + 1) % 3) # 合并后新颜色为:(旧颜色 + 1) % 3
(4)确定答案
(1) 如果f[i][j] != INF说明最终合并成一堆,且f[i][j]就是最小值
(2) 如果不能合并成一堆,枚举最少能合并的堆数i,2 <= i <= n。从2开始,从小到大,最多n堆。
AC代码:
INF = 100000000
def dfs(u, start):
global res
if u == j:
t, a = 0, 1
for k in range(j):
t += f[a][cnt[k]]
a = cnt[k] + 1
t += f[a][n]
res = min(res, t)
return
for i in range(start, n):
if not st[i]:
st[i] = 1
cnt[u] = i
dfs(u + 1, i + 1)
st[i] = 0
n = int(input())
w = [0] + list(map(int, input().split()))
for i in range(1, n + 1): w[i] += w[i - 1]
c = [0] + list(map(int, input().split()))
f = [[0] * (n + 1) for _ in range(n + 1)]
g = [[-1] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1): g[i][i] = c[i]
for lg in range(2, n + 1): # 思路和算法基础课《石子合并》一样,不过要判断颜色是否相同
for i in range(1, n + 2 - lg):
j = i + lg - 1
f[i][j] = INF
for k in range(i, j):
if g[i][k] == g[k + 1][j]: # 如果两堆石子颜色相同,g[i][j]表示区间[i, j]的颜色
if f[i][j] > f[i][k] + f[k + 1][j] + w[j] - w[i - 1]:
f[i][j] = f[i][k] + f[k + 1][j] + w[j] - w[i - 1]
g[i][j] = ((g[i][k] + 1) % 3) # 合并后新颜色为:(旧颜色 + 1) % 3
if f[1][n] != INF:
print(1, f[1][n])
else:
res = INF
for i in range(2, n): # i:最少能合并为i堆,从小到大枚举
j = i - 1 # 合并为i堆: (n - 1)位置插入(i - 1)个隔板
cnt = [0] * j # 例如:5个石子中间有4个空能插隔板,分成2堆要插1个隔板,分成3堆要插2个隔板
st = [0] * (n + 1)
dfs(0, 1) # 枚举所有隔板位置的插法,取最小值
if res != INF: # res被跟能够合成i堆,输出res就行了
print(i, res)
exit()