両腕秤

4547 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年2月10日午後2:20

インプリメンテーションコード

# 양팔저울
import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, sum):
    global res
    if L == k:
        if 0<sum<=s:
            res.add(sum)
    else:
        DFS(L+1, sum+weight[L])
        DFS(L+1, sum-weight[L])
        DFS(L+1, sum)

if __name__ == "__main__":
    k = int(input())
    weight = list(map(int, input().split()))
    s = sum(weight)
    res = set()
    DFS(0, 0)
    print(s-len(res))
  • を左に追加するとsumに重量が加算され、右にするとsumに重量が減算されます.そのボタンをまったく置かなければ、総数を直接彼に渡します.
  • のすべてのボタンは、左、ああ、放さないと、このような3つの状況を調べると、最終的に対称構造が現れ、結果値が負、正数の場合対称になります.絶対値は等しく、res(正の場合)
    • に追加されたのは1つだけです.
    コインを替える
    0415迷宮脱出任務未完成