用單調(diào)性優(yōu)化動態(tài)規(guī)劃

1、JSOI2009集訓(xùn)隊論文1用單調(diào)性優(yōu)化動態(tài)規(guī)劃用單調(diào)性優(yōu)化動態(tài)規(guī)劃【摘要摘要】單調(diào)性作為一類重要的性質(zhì)，在信息學(xué)競賽中是一種極為常見的解題突破口，也在動態(tài)規(guī)劃的優(yōu)化過程中起著至關(guān)重要的作用。本文主要選取了幾道國內(nèi)競賽試題，探討單調(diào)性在動態(tài)規(guī)劃優(yōu)化中神奇的應(yīng)用?！娟P(guān)鍵字關(guān)鍵字】單調(diào)性動態(tài)規(guī)劃隊列凸線JSOI2009集訓(xùn)隊論文3解法分析…………………………………………………………………8小結(jié)…………………………………………………………….

2、...............9三一些更復(fù)雜的例子三一些更復(fù)雜的例子…………………………………………………………..10【例三例三】ToyHNOI08….…………………………………………..………..10題目描述………………………………………………………………10樸素的解法……………………………………………………………10正確的解法……………………………………………………………10為什么決策單調(diào)？……………………………………………………

3、11【例四例四】StageZjtsc07……………………………………….………..….12題目描述………………………………………………………………12解法分析………………………………………………………………12四利用凸線的單調(diào)性來優(yōu)化四利用凸線的單調(diào)性來優(yōu)化Dp……………………………………………….15【例五例五】貨幣兌換貨幣兌換NOI2007………………………………………………..15題目描述………………………………………………………