boj-14888(挿入演算子)

問題自体は簡単ですが、答えはそうではありません...😭
数値が指定されている場合は、指定された演算子の数に等しい演算子を数値間に挿入します.
だからこれは得られる最高価格と最高価格の問題で、forゲートでnの中のnoの違うものが買えるようなので、そうなのでしょうか?!練習後にフォローするので後フォローで実現しました
△実は数独を解いていたとき、怒って休んでみた謙児の問題も簡単ではなかったので、もっと怒っていました.

遡及構造

その上でbacktrackingの構造を考えてみましょう.
我々が使用するbacktrackingには基本的にブランチの末尾が存在する.
例えば、N個の数列を選択した場合、N番目のステップの数を選択すると、ブランチは終了し、前のブランチに戻る.
したがって、この四半期の末尾に達すると、値を追加して続行する必要があります.
だから私は後追跡の構造を

function:
	if (분기의 끝단계인가?):
    	해당하는 값 추가
        return
    
    [분기를 진행시킬 반복문]
    
    [분기 탈출 시,
    즉 이전 단계로 돌아올 시 
    분기의 진행에 쓰였던 변수의 원상복구]

たぶんこのような構造があると思います.
これに基づいて、この問題を考え、解いた.

に答える

問題そのものは難しくない問題は、変なところでコードを書き間違えた以外はよく書けている.
宣言された変数を見てみましょうN:入力された数num_list:入力配列operator:入力する演算子を並べ替えます.sum_list:ブランチの末尾に到達すると、マージ値を格納するための配列sum:四半期ごとの合計tmp:ブランチ終了後に復元可能な変数
コードを見てみましょう

def func(num):
    global sum
    if num == N:
        sum_list.append(sum)
        return
    
    for i in range(len(operator)):
        if operator[i] != 0:
            if i == 0:
                tmp = sum
                sum += num_list[num]
                
                operator[i] -= 1
                func(num+1)
                operator[i] += 1
                
                # sum -= num_list[num]
                sum = tmp

            elif i ==  1:
                tmp = sum
                sum -= num_list[num]
                
                operator[i] -= 1
                func(num+1)
                operator[i] += 1
                
                # sum += num_list[num]
                sum = tmp

            elif i == 2:
                tmp = sum
                sum *= num_list[num]
                
                operator[i] -= 1
                func(num+1)
                operator[i] += 1
                
                # sum = sum // num_list[num]
                sum = tmp

            elif i == 3:
                tmp = sum
                if sum < 0:
                    sum = (abs(sum) // num_list[num]) * (-1)
                else:
                    sum = sum // num_list[num]
                
                operator[i] -= 1
                func(num+1)
                operator[i] += 1
                
                sum = tmp

N = int(input())
num_list = list(map(int, input().split(" ")))
operator = list(map(int, input().split(" ")))

tmp = 0 
sum_list = []
sum=num_list[0]

func(1)

print(max(sum_list))
print(min(sum_list))

入力を受信すると、最初のsumにはすでに最初の数字num_list[0]があります.
これは,演算子を追加する際に先頭の位置を入れる必要がなく,先頭の位置から考えるためである.
関数では、sumをグローバル変数として使用すると宣言し、関数を実行します.
最初から見ましょう.
上記の基本構造によれば、

if num == N:
        sum_list.append(sum)
        return

インデックスに入る数(num)が数字の末尾(N)に達すると、これまで計算されたsumをsum_listに入れる条件文となる.
第二に、operatorの数字は、演算子の個数である.
各数
+,-*,個数を
これらのケースの繰り返しを振り返ってみましょう.

for i in range(len(operator)):
        if operator[i] != 0:
            if i == 0:
                tmp = sum
                sum += num_list[num]
                
                operator[i] -= 1
                func(num+1)
                operator[i] += 1
                
                # sum -= num_list[num]
                sum = tmp

forの複文で、operatorの配列を返します.opreatorの値が0でない場合、演算子の個数が0でない場合は、次の操作を行います.
前述したように、インデックスによって計算方法が異なるため、インデックスに基づいて条件文を作成し、状況に応じて操作を実行する必要があります.
一般的に体現されている内容は同じで、加算を見たいときです.i = 0の場合、
まずtmp = sumをします.sumと入力したら、先に保存します.
あなたが幽霊から抜け出したとき、元の値に戻るために、その方法は
入力値

を保存し、値

を再割り当てます.

演算による逆演算の方法

この2つの方法があります.しかし、最初の方法を選ぶには理由があります.
それは後で説明しましょう
その後、sum += num_list[num]を介してsumに対応するインデックス数を加算する.
演算が行われているため、operator[i] -= 1によって対応する演算子が1つ減少する.
その後、func(num+1)を介して、次のインデックスのカウントの再帰が伝達される.
回帰後、operator[i] += 1を介してインデックスの演算子の個数を加算する、元の状態に戻るプロセスが必要です.
先ほど保存した一時変数tmpの値をsumに再代入します.
書き換えコード

if num == N:
        sum_list.append(sum)
        return

終点に到達すると、sumに追加されて終了する.

に質問

他の演算はすべて良いですが、常に除算を含む演算を行うと、答えに大きな誤差が生じます.
調整してみたが、結局問題はなく、計算がよくて、どこが間違っているのか分からないので、私はまた問題を読みました.
除算は整数除算しか取れません.負数を正数で割った場合、正数で置き換えて、1部取って、それを負数に変えます.
C++除算を使用します.
だから私はPythonの中で負数の除算をした後にPythonのしたのが異なっていることを発見します...ははは
例えば、Python.
Python:−5//2=−3Python : -5//2= -3Python:−5//2=−3
計算します.一般的な計算と同じかもしれませんが、残りは譲受人の場合で計算されます.
でも低計算で実現すれば
C++:−5//2=−2C++ : -5//2 = -2C++:−5//2=−2
このような計算結果が得られた.
だから除法の過程で、別の方法が必要です.

elif i == 3:
                tmp = sum
                if sum < 0:
                    sum = (abs(sum) // num_list[num]) * (-1)
                else:
                    sum = sum // num_list[num]
                
                operator[i] -= 1
                func(num+1)
                operator[i] += 1
                
                sum = tmp

除算インデックスを超えた場合(i=3)sum値が負数か譲受数かから判断します.
正数であれば、除算分を直接計算します.
負数であればsumの節値単位で計算し、負数を付ける方式で行います.
この過程では、逆演算が非常に複雑であるため、上述した一時変数tmpによってsumが保存され、その後、対応する方法で解決される.

の最後の部分

最近背越式の练习车の问题をしていますとても难しいです...
この問題も長い間悩んでいた.
backtrackingがどのように動作するかを考慮していない場合は、各ステップに必要な変数のデバッグを出力することで何回か観察することが重要であるようです.
感じられないときは、確かにデバッグして、頭の中に構造が描かれているようです.

Python 3とPyPy 3の2つを入れて、Pythonが出るのはずっと速いです.参照...