發表新討論
#38968: 請教這題要怎麼做


s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [61.223.232.64]
最後登入時間 ：
2024-05-13 16:04:44
m934. 4. 合併成本 -- 2024年1月APCS | From: [118.165.10.54] | 發表日期 : 2024-01-07 17:47

我完全不懂

 
#38969: Re: 請教這題要怎麼做


liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [122.116.111.175]
最後登入時間 ：
2024-05-19 23:56:22
m934. 4. 合併成本 -- 2024年1月APCS | From: [118.166.133.62] | 發表日期 : 2024-01-07 18:11

我完全不懂


這題是dp的經典題

https://atcoder.jp/contests/dp/tasks/dp_n
這題的轉移式改一點點就行

 
#38970: Re: 請教這題要怎麼做


s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [61.223.232.64]
最後登入時間 ：
2024-05-13 16:04:44
m934. 4. 合併成本 -- 2024年1月APCS | From: [118.165.10.54] | 發表日期 : 2024-01-07 18:19

我完全不懂


這題是dp的經典題

https://atcoder.jp/contests/dp/tasks/dp_n
這題的轉移式改一點點就行


感謝

看來DP我根本沒搞懂

 
#38972: Re: 請教這題要怎麼做


liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [122.116.111.175]
最後登入時間 ：
2024-05-19 23:56:22
m934. 4. 合併成本 -- 2024年1月APCS | From: [101.12.27.38] | 發表日期 : 2024-01-07 18:54

我完全不懂


這題是dp的經典題

https://atcoder.jp/contests/dp/tasks/dp_n
這題的轉移式改一點點就行


感謝

看來DP我根本沒搞懂

 

大概的想法是

對於一個數列 $\{a_0, a_1, a_2, a_3, a_4\}$ 要把它全部合併起來
可由以下四種情況合併而來
合併 $\{a_0\}$ $\{a_1, a_2, a_3, a_4\}$
合併 $\{a_0, a_1\}$ $\{a_2, a_3, a_4\}$
合併 $\{a_0, a_1, a_2\}$ $\{a_3, a_4\}$
合併 $\{a_0, a_1, a_2, a_3\}$ $\{a_4\}$

選最好的即可

所有區間分別合併起來的最佳解用陣列存下來，需要時(上述找最佳合併方式)直接提取即可。

至於再詳細一點的解法，你可以等個兩天，就會有一些 $APCS$ 解題報告的狂熱分子畫圖給你看了XD

 
#38973: Re: 請教這題要怎麼做


s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [61.223.232.64]
最後登入時間 ：
2024-05-13 16:04:44
m934. 4. 合併成本 -- 2024年1月APCS | From: [118.165.10.54] | 發表日期 : 2024-01-07 19:06

我完全不懂


這題是dp的經典題

https://atcoder.jp/contests/dp/tasks/dp_n
這題的轉移式改一點點就行


感謝

看來DP我根本沒搞懂

 

大概的想法是

對於一個數列 $\{a_0, a_1, a_2, a_3, a_4\}$ 要把它全部合併起來
可由以下四種情況合併而來
合併 $\{a_0\}$ $\{a_1, a_2, a_3, a_4\}$
合併 $\{a_0, a_1\}$ $\{a_2, a_3, a_4\}$
合併 $\{a_0, a_1, a_2\}$ $\{a_3, a_4\}$
合併 $\{a_0, a_1, a_2, a_3\}$ $\{a_4\}$

選最好的即可

所有區間分別合併起來的最佳解用陣列存下來，需要時(上述找最佳合併方式)直接提取即可。

至於再詳細一點的解法，你可以等個兩天，就會有一些 $APCS$ 解題報告的狂熱分子畫圖給你看了XD


謝謝

 

我在考試最後幾分鐘有畫出上面的但是已經來不及了

我再找時間自己做做看 或是看大哥的解題報告

 
#39032: Re: 請教這題要怎麼做


s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [61.223.232.64]
最後登入時間 ：
2024-05-13 16:04:44
m934. 4. 合併成本 -- 2024年1月APCS | From: [118.165.10.54] | 發表日期 : 2024-01-08 17:16

我完全不懂


這題是dp的經典題

https://atcoder.jp/contests/dp/tasks/dp_n
這題的轉移式改一點點就行


感謝

看來DP我根本沒搞懂

 

大概的想法是

對於一個數列 $\{a_0, a_1, a_2, a_3, a_4\}$ 要把它全部合併起來
可由以下四種情況合併而來
合併 $\{a_0\}$ $\{a_1, a_2, a_3, a_4\}$
合併 $\{a_0, a_1\}$ $\{a_2, a_3, a_4\}$
合併 $\{a_0, a_1, a_2\}$ $\{a_3, a_4\}$
合併 $\{a_0, a_1, a_2, a_3\}$ $\{a_4\}$

選最好的即可

所有區間分別合併起來的最佳解用陣列存下來，需要時(上述找最佳合併方式)直接提取即可。

至於再詳細一點的解法，你可以等個兩天，就會有一些 $APCS$ 解題報告的狂熱分子畫圖給你看了XD


謝謝

 

我在考試最後幾分鐘有畫出上面的但是已經來不及了

我再找時間自己做做看 或是看大哥的解題報告

剛剛過了

這題用遞迴比較簡單

用STACK做不好做

懂DP的地方就清楚了

def f(s,d,l,r):
    if l==r:return(s[l],0)
    if (l,r) in d:return d[(l,r)]
    mcost,nsu=float('inf'),0
    for m in range(l,r):
        a=f(s,d,l,m)
        b=f(s,d,m+1,r)
        cost=a[1]+b[1]+abs(a[0]-b[0])
        if mcost>cost:
            mcost=cost
            nsu=a[0]+b[0]
    d[(l,r)]=(nsu,mcost)
    return(nsu,mcost)
def main():
    from sys import stdin
    n=int(stdin.readline())
    s=list(map(int,stdin.readline().split()))
    d=dict()
    print(f(s,d,0,n-1)[1])
if __name__=="__main__":main()



 
ZeroJudge Forum