BJ 2798ブラックジャック

8292 ワード

もし問題があったら?
私が試した方法
  • N枚のカードを配列として入力、
  • を使用して、グループを再帰的に求める.
  • しかし、この過程でカードの合計がMを超えると、その組み合わせの探索は停止する.(枝切り)
    (分枝効率を向上するために降順にカードを配列する)
  • def nCr(r, n, start, total):
        global ans
        if total > M:
            return
    
        if not r:
            if ans < total:
                ans = total
            return
    
        for i in range(start, n):
            if not used[i]:
                used[i] = 1
                nCr(r-1, n, i+1, total + cards[i])
                used[i] = 0
    
    
    # N = 카드의 개수 / M = 목표 숫자(카드 3장의 합은 M을 넘지 않고 가장 가깝게)
    N, M = map(int, input().split())
    cards = sorted(list(map(int, input().split())), reverse=True)
    ans = 0
    used = [0] * N
    nCr(3, N, 0, 0)
    print(ans)
    浮気をする
    💡 組み合わせを探している間に、for재귀であることがわかります.
    この時間はいつも재귀を使っていますが、もちろん復帰する部分もあります.
    しかし,この問題は固定されたr値を有するため,forゲートで完全に解決できる.今回を机に、もう一度练习して、习惯のように问题を解决するのもいいですが、どれが効率的なのか、どれが选択できるのかを多様に近づけるように努力しなければなりません.
    
    # for를 이용해서 전체 조합 다 구해보기
    N, M = map(int, input().split())
    cards =list(map(int, input().split()))
    ans = 0
    
    for i in range(0, N-2):
        for j in range(i+1, N-1):
            for k in range(j+1, N):
                total = cards[i] + cards[j] + cards[k]
                if ans < total <= M:
                    ans = total
    
    print(ans)