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


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.89.50]
最後登入時間 ：
2025-09-24 12:11:30
g278. 4. 美食博覽會 -- 2021年9月 APCS
| From: [111.243.68.235] | 發表日期: 2021-09-06 18:22

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

#27007: Re:有人有想法嗎


cthbst (吳宗達)

學校 : 國立交通大學
編號 : 19791
來源 : [1.163.230.80]
最後登入時間 ：
2025-09-07 19:04: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.89.50]
最後登入時間 ：
2025-09-24 12:11:30
g278. 4. 美食博覽會 -- 2021年9月 APCS
| From: [111.243.68.235] | 發表日期: 2021-09-06 19:40

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

ZeroJudge Forum