AcWing 3503. 数组划分Python之DP&&DFS
原题链接
简单
作者:
是小肖啊
,
2022-04-27 21:36:03
,
所有人可见
,
阅读 275
题解
DP(只能过一半样例)
a=[0]+list(map(int,input().split()))
a.sort()
target=sum(a)//2
n=len(a)
dp=[[False for i in range(target+1)]for j in range(n)]
dp[0][0]=True
for i in range(1,n):
for j in range(target+1):
dp[i][j]=dp[i-1][j]
if j>=a[i]:
dp[i][j]=dp[i][j] or dp[i-1][j-a[i]]
for i in range(target,-1,-1):
if dp[-1][i]==True:
ans=i
break
print(sum(a)-ans,ans)
DFS&剪枝(AC)
def dfs(cur,cursums):
global ans
if cursums==target:
ans=cursums
return True
if cursums>target:
return False
if cur==n:
return False
ans=max(ans,cursums)
for i in range(cur+1,n):
if a[i]>=target:
ans=sums-a[i]
return True
if dfs(i,cursums+a[i]):
return True
return False
a=list(map(int,input().split()))
sums=sum(a)
target=sums//2
ans=-1
n=len(a)
dfs(-1,0)
print(sums-ans,ans)