高中生程式解題系統

#38968: 請教這題要怎麼做

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

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [223.137.72.55]
最後登入時間：
2024-12-11 13:02:15

m934. 4. 合併成本 -- 2024年1月 APCS | From: [118.165.10.54] | 發表日期 : 2024-01-07 17:47

我完全不懂

| 回應文章 | 回原始文章

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

liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [115.165.193.193]
最後登入時間：
2025-04-02 11:25:14

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
來源 : [223.137.72.55]
最後登入時間：
2024-12-11 13:02:15

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
來源 : [115.165.193.193]
最後登入時間：
2025-04-02 11:25:14

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}}$

選最好的即可

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

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

| 回應文章 | 回原始文章

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

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

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [223.137.72.55]
最後登入時間：
2024-12-11 13:02:15

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}}$

選最好的即可

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

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

謝謝

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

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

| 回應文章 | 回原始文章

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

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

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [223.137.72.55]
最後登入時間：
2024-12-11 13:02:15

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}}$

選最好的即可

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

至於再詳細一點的解法，你可以等個兩天，就會有一些 $A P C S$ 解題報告的狂熱分子畫圖給你看了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