方法一$DFS剪枝TLE$
class Solution:
def minimumIncompatibility(self, nums: List[int], k: int) -> int:
if k==len(nums):
return 0
cnt = collections.Counter(nums)
maxi = max(cnt[x] for x in cnt)
if maxi>k:
return -1
n = len(nums)
nums.sort()
self.res = float('inf')
tmp = collections.defaultdict(list)
lens = n//k
for i in range(k):
tmp[k]=[]
vis = set()
def check(path):
sums = 0
for x in path:
if path[x]:
sums+=max(path[x])-min(path[x])
return sums>self.res
def dfs(path,resi,cntk):
if resi==0:
self.res = min(self.res,sum(max(path[i])-min(path[i]) for i in range(k)))
return
if check(path):
return
for i in range(n):
if i not in vis and nums[i] not in path[cntk]:
path[cntk].append(nums[i])
vis.add(i)
dfs(path,resi-1,cntk+1) if len(path[cntk])==lens else dfs(path,resi-1,cntk)
path[cntk].pop()
vis.remove(i)
dfs(tmp,n,0)
return self.res
$方法二 状压dp$
f[i] 已经凑好了若干组 且已经用的数为i的所有方案中的最小值
闫式dp分析
子集j为i这种情况下 最后一组加入的组为子集j,
则j加入前的所有方案的最小值=f[i-j],
加入j则需要加上子集j的兼容性g[j],
那么从j转移到i f[i] = f[i-j] + g[j]
然鹅y总的这套状压dp python下还是TLE(懂了这就放弃用python打周赛 然鹅python写起来是真的快啊不想弃啊)
枚举子集原理看这位的
class Solution:
def minimumIncompatibility(self, nums: List[int], k: int) -> int:
n = len(nums)
if k==n:
return 0
if k==1:
cnt = collections.Counter(nums)
return max(nums)-min(nums) if all(cnt[x]==1 for x in cnt) else -1
g = [-1]*(1<<n)#状态i的兼容性数组
f = [float('inf')]*(1<<n)#状态i的最小兼容性和
f[0]=0
def cnt1(x):
res = 0
while x:
x=x&(x-1)
res+=1
return res
for i in range(1,1<<n):
if cnt1(i)!=n//k:
continue
d = []
for j in range(n):
if (i>>j) & 1:
d.append(nums[j])
flag = False
d.sort()
for j in range(len(d)-1):
if d[j]==d[j+1]:
flag = True
break
if flag:#如果状态i下 子集d中有相同的两个数
continue
g[i] = d[-1]-d[0]#状态i下 兼容性g[i]
for i in range(1,1<<n):#枚举i的所有子集j O(3^n)
if cnt1(i)%(n//k):continue
j = i
while j>0:
if g[j]!=-1:
f[i] = min(f[i],f[i-j]+g[j])
j = (j-1)&i
res = f[(1<<n)-1]
return res if res!=float('inf') else -1