發表新討論
#27006: 有人有想法嗎


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.253.147]
最後登入時間 ：
2024-10-03 15:39:22
g278. 4. 美食博覽會 -- 2021年9月APCS | From: [111.243.68.235] | 發表日期 : 2021-09-06 18:22

這題看到的當下知道要用dp，但沒有想到關係式，所以只做了k=1的情況

 
#27007: Re:有人有想法嗎


cthbst (吳宗達)

學校 : 國立交通大學
編號 : 19791
來源 : [1.163.213.15]
最後登入時間 ：
2024-10-22 08:34:42
g278. 4. 美食博覽會 -- 2021年9月APCS | From: [140.113.207.98] | 發表日期 : 2021-09-06 18:49

這題看到的當下知道要用dp，但沒有想到關係式，所以只做了k=1的情況


dp(i, k) := 考慮前 i 個攤商, 有 k 個人
dp(i, k) = dp(j, k - 1) + (i - j), 其中 [j + 1, i] 是以 i 為結尾最長組成都不同的區間

 
#27010: Re:有人有想法嗎


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.253.147]
最後登入時間 ：
2024-10-03 15:39:22
g278. 4. 美食博覽會 -- 2021年9月APCS | From: [111.243.68.235] | 發表日期 : 2021-09-06 19:40

做出來了，謝謝演算法海牛！

 
ZeroJudge Forum