cjy基礎(chǔ)動(dòng)態(tài)規(guī)劃

P2219 [HAOI2007]修筑綠化帶

對(duì)于一個(gè)nm的矩形空間內(nèi)，然后選擇一個(gè)ab的矩形加上它所在部分的權(quán)值，然后在內(nèi)部再選擇一個(gè)c*d的矩形，然后減去它的權(quán)值和，求解最大的權(quán)值。

首先我們可以通過(guò)枚舉求得所有右下角對(duì)應(yīng)位置的矩形大小內(nèi)的權(quán)值和，然后我們要求的就是另一個(gè)矩形范圍內(nèi)的權(quán)值最小值，這樣我們就把問(wèn)題轉(zhuǎn)化為了求解所有等大小矩形范圍內(nèi)的最小值，那么有一個(gè)經(jīng)典的單調(diào)隊(duì)列技巧可以解決這個(gè)問(wèn)題，在兩維上分別處理最小值。

P3943 星空

對(duì)于給定01串，有k個(gè)地方是0，然后可以選擇m種長(zhǎng)度區(qū)間取反，求解最小需要多少次能夠?qū)⒄麄€(gè)01串變成1。
k<=8,m<=64

首先區(qū)間問(wèn)題難以處理，我們先差分將區(qū)間操作轉(zhuǎn)化為兩個(gè)點(diǎn)反轉(zhuǎn)，然后關(guān)注兩個(gè)操作點(diǎn)之間的距離，發(fā)現(xiàn)可以加減，然后我們不能枚舉所有2^n但是這個(gè)問(wèn)題，因?yàn)橹涤蚍秶苄?#xff0c;所以可以背包，然后求解產(chǎn)生某個(gè)長(zhǎng)度的最小次數(shù)。

然后對(duì)于可加可減可以將負(fù)的值也作為物品來(lái)處理。

最后對(duì)于每一個(gè)狀態(tài)，我們需要進(jìn)行狀壓dp，每次一定是將某兩個(gè)點(diǎn)一起消除，或者單點(diǎn)消除，我們已經(jīng)獲得了對(duì)應(yīng)的花費(fèi)就可以dp了。

總結(jié)

以上是生活随笔為你收集整理的cjy基础动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。