Pythonアルゴリズム075|最高のタワー**

75.最も高い塔を建てる
下に正方形の六面体レンガで塔を建てたいです.塔のレンガの下には
上から上へ積み上げて作る.以下の条件を満たす場合、最も高い塔を建てることができる
ログに記入してください.
(条件1)レンガが回らない.すなわち、側面を底部として使用することはできない.
(条件2)底幅が等しい煉瓦も、重量が等しい煉瓦もない.
(条件3)レンガの高さは同じである可能性がある.
(条件4)塔を建てる場合、底の狭いレンガには底の広いレンガを置くことができません.
(条件5)重煉瓦を軽煉瓦の上に置くことはできません.
■説明の入力
入力ファイルの最初の行には、入力するレンガの数が表示されます.入力タイルの数が最も多い
100個です.2行目の最初は、行ごとにレンガに関する情報です.レンガの底の幅、レンガの高さです.
次に、重量を正の整数に順番に与えます.各ブロックは入力順に1から連続しています
人号を持つ.
■出力説明
最初の列で一番高く積み上げられる塔の高さを出力します.
■入力例1
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2
■出力例1
10
韓国情報
『私の答え』
よく答えたと思いますが、例1でのみ正解でした.
=>
こんな状況ではだめだ.

ar=[0]
h=[0]
w=[0]
n=int(input())
for i in range(n) :
    a,b,c=map(int,input().split())
    ar.append(a)
    h.append(b)
    w.append(c)
dy=[0]*(n+1)
dy[1]=min(h)
for i in range(1,n+1) :
    s=0
    for j in range(1,n+1):
        if ar[i]>ar[j] and w[i]>w[j] :
            s+=h[j]
        dy[i]=h[i]+s
print(dy)

=>実行中に発生したエラー
dyでmaxを更新するはずでしたが、hで更新しました

ar=[0]
h=[0]
w=[0]
n=int(input())
k=[]
for i in range(n) :
    (a,b,c)=map(int,input().split())
    k.append((a,b,c))
    k.sort(reverse=True)
for i in range(len(k)) :
    ar.append(k[i][0])
    h.append(k[i][1])
    w.append(k[i][2])
dy=[0]*(n+1)
dy[1]=h[1]
for i in range(1,n+1) :
    maxx=0
    s=0
    for j in range(i) :
        if w[i]<w[j] and dy[j]>maxx : #만약 밑에 여러개의 벽돌이 올 수 있으면 dy중에서 맥스인것으로..
            maxx=dy[j]
    dy[i]=h[i]+maxx
print(max(dy))

<解答>

初期時に幅の大きい順に並べ、幅、高さ、重量を1回ごとに配置する

.

は、各レンガが底部にあると仮定するのではなく、頂部に位置し、それに近いと仮定する.

dyは自分と一緒に自分の下に来ることができる子供たちより高い

そして私の前にいる子供たちは、彼らの幅が私より大きくなったので、重さしかありません.
確認してくださいもし前の子供が私より重いなら、彼は私の下に来ることができます.
だから、この子のためにdy[j]+h[i]をすればいい

if __name__=="__main__":
    n=int(input())
    bricks=[]
    for i in range(n):
        a, b, c=map(int, input().split())
        bricks.append((a, b, c))
    bricks.sort(reverse=True)
    dy=[0]*n
    dy[0]=bricks[0][1]
    res=bricks[0][1];
    for i in range(1, n):
        max_h=0;
        for j in range(i-1, -1, -1):
            if bricks[j][2]>bricks[i][2] and dy[j]>max_h:
                max_h=dy[j]
        dy[i]=max_h+bricks[i][1]
        res=max(res, dy[i])
    print(res)

『反省点』

無視する部分が非常に多い.dyに蓄積することを忘れないでください

『学んだこと』

が乱雑であれば、並べ替えて1つの基準を基準に

にアクセスする.
<第2ラウンド解答>
=>例4、例5の答えは正解1より少ない.どの部分が間違っていますか?

n=int(input())
tot=[]
for i in range(n) :
    s,h,w= map(int,input().split())
    tot.append((s,h,w))
tot.sort(reverse=True)
tot.insert(0,0)
dy=[0]*(n+1)
dy[1]=tot[1][1]
for i in range(2,n+1) :
    maxi=-1
    for j in range(1,i):
        if tot[j][2]>tot[i][2] and dy[j]>maxi:
            maxi=dy[j]
        dy[i]=maxi+tot[i][1]
print(max(dy))