試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

您的背景令人讚嘆，沒想到也有涉略程式設計，真是太厲害了！

謝謝你的分享，對於較困難的測資，除了DP，還有什麼改進方向可以選擇呢？

試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

您的背景令人讚嘆，沒想到也有涉略程式設計，真是太厲害了！

謝謝你的分享，對於較困難的測資，除了DP，還有什麼改進方向可以選擇呢？

優化過的DP

試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

您的背景令人讚嘆，沒想到也有涉略程式設計，真是太厲害了！

謝謝你的分享，對於較困難的測資，除了DP，還有什麼改進方向可以選擇呢？

優化過的DP

Orz

試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

extra 的題解
https://hackmd.io/@peienwu/APCS0904

試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

extra 的題解
https://hackmd.io/@peienwu/APCS0904

題解的程式是錯的，不知道是不是故意不要讓我們複製貼上，可是因此我看了以後還是不懂要怎麼解。

我目前最大的問題點就是照他的DP，如果連續4個攤販賣一樣的東西，不管p是多少，都會有以下行動

假設那4個攤販的編號分別是i,i+1,i+2,i+3，當DP掃過去的時候，dp[i+1]得到i前面「應該是最大值的數字」，然後加上一個只吃一個攤販的試吃員

然後可怕的來了，根據他的程式，dp[i+3]一定是dp[i+1]加上一個新的試吃員，也就是說一定會有一個試吃員只吃一個攤販，而後面也會保留這個試吃員。

我沒有想到要怎麼改進這個程式，還請大神指教

試試更為困難的版本：

題敘相同，但限制改為 n<=100000, k<=100000, 攤販的值<=100000。(注意 n*k 無限制)

extra 的題解
https://hackmd.io/@peienwu/APCS0904

題解的程式是錯的，不知道是不是故意不要讓我們複製貼上，可是因此我看了以後還是不懂要怎麼解。

 

我目前最大的問題點就是照他的DP，如果連續4個攤販賣一樣的東西，不管p是多少，都會有以下行動

假設那4個攤販的編號分別是i,i+1,i+2,i+3，當DP掃過去的時候，dp[i+1]得到i前面「應該是最大值的數字」，然後加上一個只吃一個攤販的試吃員

然後可怕的來了，根據他的程式，dp[i+3]一定是dp[i+1]加上一個新的試吃員，也就是說一定會有一個試吃員只吃一個攤販，而後面也會保留這個試吃員。

 

我沒有想到要怎麼改進這個程式，還請大神指教

好欸我改好了 謝謝