題目

題目描述 商店正在出售小C最喜歡的系列玩具，在接下來(lái)的n周中，每周會(huì)出售其中 的一款，同一款玩具不會(huì)重復(fù)出現(xiàn)。
由于是小C最喜歡的系列，他希望盡可能多地購(gòu)買這些玩具，但是同一款玩 具小C只會(huì)購(gòu)買一個(gè)。同時(shí)，小C的預(yù)算只有m元，因此他無(wú)法將每一款都納入 囊中。此外，小C不能連續(xù)兩周都購(gòu)買玩具，否則他會(huì)陷入愧疚。現(xiàn)在小C想知 道，他最多可以買多少款不同的玩具呢？ 輸入 輸入文件共2行； 第一行兩個(gè)正整數(shù)n和m，中間用一個(gè)空格隔開(kāi)； 第二行共n個(gè)正整數(shù)，第i個(gè)正整數(shù)表示第i周出售的玩具的價(jià)格。 輸出 輸出文件只有一行，包含一個(gè)整數(shù)，表示小C最多能買多少款不同的玩具。 樣例輸入 3 8 4 4 5 樣例輸出 1 提示 對(duì)于30%的數(shù)據(jù)，n≤10； 對(duì)于60%的數(shù)據(jù)，n≤100，m≤1000；
對(duì)于100%的數(shù)據(jù)，n≤1000，m≤1000000，單個(gè)玩具的價(jià)格≤1000。

分析

　　因?yàn)椤巴豢钔婢咝只會(huì)購(gòu)買一個(gè)”，所以很明顯是0-1背包（買或不買）。又因?yàn)椤安荒苓B續(xù)兩周都購(gòu)買玩具”，所以需要立flag來(lái)記錄購(gòu)買情況。

　　立flag要么狀壓，要么滾動(dòng)數(shù)組。而狀壓我才剛開(kāi)始研究，所以要滾動(dòng)數(shù)組。

代碼

?

#include<bits/stdc++.h> using namespace std; int a[1000005],n,m,x,y;//x和y記錄滾動(dòng)數(shù)組。 int dp[1000005];//dp[i]記錄花i塊錢最多能購(gòu)買到的玩具數(shù)量 bool flag[1000005][3];//dp[i][j]記錄dp[i]在上周是否購(gòu)買了玩具，j用來(lái)滾動(dòng)數(shù)組。 int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);int x=1,y=2;for(int i=1;i<=n;i++){swap(x,y);//滾動(dòng)一次flag數(shù)組。 for(int j=0;j<=m;j++) flag[j][y]=0;for(int j=m;j>=a[i];j--){if(dp[j-a[i]]+1>dp[j]&&!flag[j-a[i]][x]){flag[j][y]=1;dp[j]=dp[j-a[i]]+1;}}}printf("%d",dp[m]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/DARTH-VADER-EMPIRE/p/11363116.html

總結(jié)

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

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