一個(gè)長(zhǎng)度為n的字符串，操作A可以把字符串第一個(gè)字母移動(dòng)到最后一個(gè)，其他位置保持不變，操作B可以把一個(gè)字符變成其他任意字符。操作A，操作B的費(fèi)用分別為A,B請(qǐng)問把這個(gè)字符串變成回文需要花費(fèi)多少。

我們發(fā)現(xiàn)操作1和操作2的順序是不影響結(jié)果的，我們可以暴力枚舉一下即可，數(shù)據(jù)5000，可以跑過去。

N種硬幣，第i種有Bi個(gè)價(jià)值A(chǔ)i，我們是否可以組合出價(jià)值為X的組合，是輸出Yes,否輸出No.

經(jīng)典背包問題，多重背包，我們可以拆分為多個(gè)01背包，涉及方案數(shù)問題，統(tǒng)計(jì)類背包，需要將初始化f[0]=1,f[j]+=f[j-a],這樣子只有當(dāng)恰好組合出價(jià)值為X的方案時(shí)我們f[x]才會(huì)增加，并且f[x]的值就是組合出價(jià)值為X的方案總數(shù)。

題目大意

給定一張有向圖，邊權(quán)均為1，給定點(diǎn)權(quán)。

有?q個(gè)詢問，每個(gè)詢問問從x點(diǎn)到?y點(diǎn)，其邊權(quán)和最小是多少，在最小的前提下，點(diǎn)權(quán)和最大是多少。不能到達(dá)則輸出?Impossible。

解題思路

Floyd 的應(yīng)用。為了方便轉(zhuǎn)移，一段長(zhǎng)度大于1?的路徑中紀(jì)念品的總價(jià)值先不計(jì)算起點(diǎn)，等到最后統(tǒng)計(jì)時(shí)再加上。注意只有邊數(shù)更短，或者相同邊數(shù)且紀(jì)念品總價(jià)值更高時(shí)才能更新。

代碼展示