題意：

思路：

我們先來考慮如何獲得小t所需要的貨幣總數(shù)。

因?yàn)閿?shù)據(jù)是有序的，我們可以從大到小來枚舉。

int cal(int x) { int id = n; int" />

国产成人精品无码青草_亚洲国产美女精品久久久久∴_欧美人与鲁交大毛片免费_国产果冻豆传媒麻婆精东

18143453325 或 在線咨詢 在線咨詢
18143453325 或 在線咨詢
所在位置： 首頁 > 營銷資訊 > 網(wǎng)站運(yùn)營 > (DP) 代碼源每日一題 Div1 貨幣系統(tǒng)

(DP) 代碼源每日一題 Div1 貨幣系統(tǒng)

時(shí)間：2023-04-21 15:36:02 | 來源：網(wǎng)站運(yùn)營

時(shí)間：2023-04-21 15:36:02 來源：網(wǎng)站運(yùn)營

(DP) 代碼源每日一題 Div1 貨幣系統(tǒng)：題目鏈接：Daimayuan Online Judge

題意：

思路：

我們先來考慮如何獲得小t所需要的貨幣總數(shù)。

因?yàn)閿?shù)據(jù)是有序的，我們可以從大到小來枚舉。

int cal(int x) { int id = n; int cot = 0; while (x) { while (a[id] > x)id--; cot += x / a[id]; x -= x / a[id] * a[id]; } return cot;}最少貨幣數(shù)可以通過完全背包來獲得，問題是背包的容量。

這里我猜了一發(fā)結(jié)論，就是枚舉1 到 20000 所需要的貨幣數(shù)即可，然后就交了一發(fā)，過了。

但是正確性我不會(huì)證明，但是感覺這樣很對（qwq

而且好像大家都是這樣做的。

等晚上官方題解出了，我再補(bǔ)一個(gè)證明吧。

code

int cal(int x) { int id = n; int cot = 0; while (x) { while (a[id] > x)id--; cot += x / a[id]; x -= x / a[id] * a[id]; } return cot;}void slove() { cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 0; i <= 20000; i++)f[i] = INF; f[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= 20000; j++) { f[j + a[i]] = min(f[j + a[i]], f[j] + 1); } } for (int i = 1; i <= 20000; i++) { if (f[i] != cal(i)) { NO; return; } } YES;}

關(guān)鍵詞：貨幣,系統(tǒng)

74
73
25
news

版權(quán)所有? 億企邦 1997-2025 保留一切法律許可權(quán)利。

為了最佳展示效果，本站不支持IE9及以下版本的瀏覽器，建議您使用谷歌Chrome瀏覽器。 點(diǎn)擊下載Chrome瀏覽器
關(guān)閉