騰訊----小Q的歌單

文章目錄

• • 騰訊----小Q的歌單
  • 一、題目描述
  • 二、分析
  • 方法一：組合
  • 方法二：動(dòng)規(guī)

一、題目描述

小Q有X首長(zhǎng)度為A的不同的歌和Y首長(zhǎng)度為B的不同的歌，現(xiàn)在小Q想用這些歌組成一個(gè)總長(zhǎng)度正好為K的歌單，每首歌最多只能在歌單中出現(xiàn)一次，在不考慮歌單內(nèi)歌曲的先后順序的情況下，請(qǐng)問(wèn)有多少種組成歌單的方法。

輸入描述:

每個(gè)輸入包含一個(gè)測(cè)試用例。 每個(gè)測(cè)試用例的第一行包含一個(gè)整數(shù)，表示歌單的總長(zhǎng)度K(1<=K<=1000)。 接下來(lái)的一行包含四個(gè)正整數(shù)，分別表示歌的第一種長(zhǎng)度A(A<=10)和數(shù)量X(X<=100) 以及歌的第二種長(zhǎng)度B(B<=10)和數(shù)量Y(Y<=100)。保證A不等于B。

輸出描述:

輸出一個(gè)整數(shù),表示組成歌單的方法取模。因?yàn)榇鸢缚赡軙?huì)很大,輸出對(duì)1000000007 取模的結(jié)果。

輸入例子1:

5 2 3 3 3

輸出例子1:

9

二、分析

方法一：組合

這道題比較好的處理方法也最容易理解的是用組合數(shù)來(lái)求解，說(shuō)到組合數(shù)就很容易想到這道題和我們高中做的從兩個(gè)盒子里取小球的排列組合題。

• 此題可以轉(zhuǎn)換為這樣一道數(shù)學(xué)題，有兩個(gè)盒子，一個(gè)盒子里裝有3個(gè)紅球，一個(gè)盒子里裝有3個(gè)白球，紅球代表2分，白球代表3分，則從兩個(gè)盒子中任意拿球使其分?jǐn)?shù)等于9的拿法有多少種。
• 這樣就會(huì)想如果拿了0個(gè)紅球，白球有多少種拿法，如果拿了1個(gè)、2個(gè)、3個(gè)紅球，白球各有多少種拿法。
• 再者，將球的數(shù)量和球的分?jǐn)?shù)換成未知的量：即有兩個(gè)盒子，一個(gè)盒子里裝有X個(gè)紅球，一個(gè)盒子里裝有Y個(gè)白球，紅球代表A分，白球代表B分，則從兩個(gè)盒子中任意拿球使其分?jǐn)?shù)等于K的拿法有多少種。
• 很顯然就和面試題一樣了，可以想到假設(shè)拿了 i 個(gè)紅球（ i <= X），需要滿(mǎn)足條件（ i * A <= K : 分?jǐn)?shù)不能超過(guò)K）&&（（ K - i* A）% B == 0 ：確保分?jǐn)?shù)相加等于K，即剩下的歌單長(zhǎng)度可以在B中組合出來(lái)） && （（ K - i* A）/ B <= Y :不能超過(guò)白球的數(shù)目），將滿(mǎn)足條件的結(jié)果相加起來(lái)就是最后的結(jié)果。
• 而當(dāng) 滿(mǎn)足條件后從各自的盒子里拿球就有不同的拿法，是很典型的排列組合問(wèn)題，對(duì)于這道題我們可以建一個(gè)二維數(shù)組來(lái)存這些組合數(shù)，行標(biāo)代表排列組合公式的下標(biāo)，列標(biāo)代表排列組合公式的上標(biāo)
• 可以直接看代碼：

#include<iostream> using namespace std;int main() {int k,a,x,b,y;long long int count = 0;long long int c[101][101];while(cin>>k){cin>>a>>x>>b>>y;//初始化c數(shù)組//c[i][j]代表從i個(gè)里面選j個(gè)共有多少種選取方法c[0][0] = 1;for(int i = 1;i <= 100;i++){c[i][0] = 1;for(int j = 1;j <= 100;j++){c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 1000000007;}}//開(kāi)始計(jì)算for(int i = 0;i <= k / a && i <= x;i++){//如果選取i個(gè)a歌單的歌曲，那么剩下的歌曲時(shí)間長(zhǎng)度為k - i * a//如果滿(mǎn)足剩下的時(shí)間可以在b中組合出來(lái)，并且需要b歌曲的數(shù)量//小于給定的y才可以//如果滿(mǎn)足條件，count就等于在x個(gè)里選取i個(gè)A長(zhǎng)度的歌的選法乘以//在y個(gè)里選取(k - i * a) / b個(gè)B長(zhǎng)度的歌的選法//最后相加即可if((k - i * a) % b == 0 && (k - i * a) / b <= y)count = (count + (c[x][i] * c[y][(k - i * a) / b])% 1000000007) % 1000000007; }cout<<count<<endl;} }

方法二：動(dòng)規(guī)

這道題和背包問(wèn)題類(lèi)似。

1. 第一步要明確兩點(diǎn)，「狀態(tài)」和「選擇」

先說(shuō)狀態(tài)，如何才能描述一個(gè)問(wèn)題局面？只要給定幾個(gè)可選的歌曲和一個(gè)長(zhǎng)度為K的限制，就形成了一個(gè)背包問(wèn)題，對(duì)不對(duì)？所以狀態(tài)有兩個(gè)，就是「歌曲組成的總長(zhǎng)度K」和「可選擇的歌」。

再說(shuō)選擇，也很容易想到啊，對(duì)于每首歌，你能選擇什么？選擇就是「裝進(jìn)背包：算上這首歌的時(shí)長(zhǎng)」或者「不裝進(jìn)背包：不算這首歌的時(shí)長(zhǎng)」嘛。

明白了狀態(tài)和選擇，動(dòng)態(tài)規(guī)劃問(wèn)題基本上就解決了，只要往這個(gè)框架套就完事兒了：

for 狀態(tài)1 in 狀態(tài)1的所有取值：for 狀態(tài)2 in 狀態(tài)2的所有取值：for ...dp[狀態(tài)1][狀態(tài)2][...] = 擇優(yōu)(選擇1，選擇2...)

2. 第二步要明確dp數(shù)組的定義

dp數(shù)組是什么？其實(shí)就是描述問(wèn)題局面的一個(gè)數(shù)組。換句話(huà)說(shuō)，我們剛才明確問(wèn)題有什么「狀態(tài)」，現(xiàn)在需要用dp數(shù)組把狀態(tài)表示出來(lái)。

首先看看剛才找到的「狀態(tài)」有兩個(gè)，也就是說(shuō)我們需要一個(gè)二維dp數(shù)組，一維表示可選擇的歌曲，一維表示歌曲總時(shí)長(zhǎng)。

dp[i][w]的定義如下：對(duì)于前i首歌曲，當(dāng)前歌曲總時(shí)長(zhǎng)為w，這種情況下組合歌曲的方法有dp[i][w]種。

比如說(shuō)，如果 dp[3][5] = 6，其含義為：對(duì)于給定的一系列歌曲中，若只對(duì)前 3 個(gè)歌曲進(jìn)行選擇，當(dāng)歌曲總時(shí)長(zhǎng)K為 5 時(shí)，最多的組合方法有6種。

根據(jù)這個(gè)定義，我們想求的最終答案就是dp[N][W]。base case 就是dp[0][…] = dp[…][0] = 0，因?yàn)闆](méi)有歌曲或者歌曲總時(shí)長(zhǎng)為0的時(shí)候，能構(gòu)選擇的組合方法就是 0種，不過(guò)我們認(rèn)為當(dāng)沒(méi)有歌曲和歌曲總時(shí)長(zhǎng)為0都滿(mǎn)足的時(shí)候認(rèn)為算一種方法，即dp[0][0] == 1。

細(xì)化上面的框架：

int dp[N+1][W+1] dp[0][..] = 0 dp[..][0] = 0for i in [1..N]:for w in [1..W]把歌曲 i 裝進(jìn)背包,不把歌曲 i 裝進(jìn)背包) return dp[N][W]

3. 第三步，根據(jù)「選擇」，思考狀態(tài)轉(zhuǎn)移的邏輯

簡(jiǎn)單說(shuō)就是，上面?zhèn)未a中「把歌曲i裝進(jìn)背包」和「不把歌曲i裝進(jìn)背包」怎么用代碼體現(xiàn)出來(lái)呢？

這一步要結(jié)合對(duì)dp數(shù)組的定義和我們的算法邏輯來(lái)分析：

先重申一下剛才我們的dp數(shù)組的定義：

dp[i][w]表示：對(duì)于前i首歌曲，當(dāng)前總時(shí)長(zhǎng)為w時(shí)，這種情況下可以組合的方法是dp[i][w]種。

如果你沒(méi)有把這第i個(gè)歌曲裝入背包，那么很顯然，最大價(jià)值dp[i][w]應(yīng)該等于dp[i?1][w]。你沒(méi)有選擇一首歌曲，總時(shí)長(zhǎng)也就不會(huì)變，那就繼承之前的結(jié)果。

如果你把這第i首歌曲裝入了背包，那么dp[i][w]應(yīng)該等于dp[i?1][w?wt[i?1]] + val[i?1]。

首先，由于i是從 1 開(kāi)始的，所以對(duì)val和wt的取值是i-1。

而dp[i?1][w?wt[i?1]]也很好理解：你如果想裝第i首歌曲，你怎么計(jì)算這時(shí)候的組合方法？換句話(huà)說(shuō)，在裝第i首歌曲的前提下，總時(shí)長(zhǎng)的最大組合方法是多少？

顯然，你應(yīng)該尋求剩余時(shí)長(zhǎng)w?wt[i?1]限制下組合的方法，加上第i首歌曲的時(shí)長(zhǎng)val[i?1]，這就是裝第i首歌曲的前提下，總時(shí)長(zhǎng)的組合方法。

4.到這里基本上一背包問(wèn)題的方式解釋了一遍本題，但是這道題是沒(méi)有每個(gè)物品 的價(jià)值的，所以需要根據(jù)單首歌曲的時(shí)長(zhǎng)構(gòu)造這樣一組價(jià)值信息

for(int i=1;i<=x;i++)len[i]=a; for(int i=x+1;i<=length;i++)len[i]=b;

5.每首歌曲的‘價(jià)值’有了，那么在什么情況下選擇加入歌曲，什么情況下不能加入歌曲？？

lens[j]表示第j首歌的長(zhǎng)度，如果當(dāng)前剩余的歌曲時(shí)長(zhǎng) >= lens[j]，那么由前j首歌組成長(zhǎng)度為i的歌單的方法數(shù)可分為兩部分，第一部分是dp[j - 1][i]，即由前j-1首歌組成長(zhǎng)度為i的歌單的方法數(shù)（不選取這首歌），第二部分是dp[j-1][i-lens[j]](選取這首歌)。

6. 如果當(dāng)前剩余的總時(shí)長(zhǎng) < lens[j]，那么dp[i][j]等于dp[i][j?1]。

代碼中dp[i][j]和上面描述有點(diǎn)不一樣（手誤）:dp[i][j]代表用j首歌組成總時(shí)長(zhǎng)i的方法有多少種，剛好寫(xiě)反了，不過(guò)道理是一樣的。

#include <iostream> #include <algorithm> #include<string.h> #include<map> #include<iterator> #include<math.h> using namespace std; const int mod = 1000000007;int k;//總時(shí)長(zhǎng) int a,x,b,y;//a代表a歌曲的長(zhǎng)度，x代表a歌曲的數(shù)量... int dp[1010][210];//dp數(shù)組 int len[210];//存儲(chǔ)每首歌的時(shí)長(zhǎng) int main() {cin>>k;cin>>a>>x>>b>>y;int length = x + y;memset(dp,0,sizeof(dp));memset(len,0,sizeof(len));//base casedp[0][0] = 1;//根據(jù)每首歌的時(shí)長(zhǎng)構(gòu)造‘價(jià)值’數(shù)組for(int i = 1;i <= x;i++)len[i] = a;for(int i = x + 1;i <= length;i++)len[i] = b;//循環(huán)for(int i = 0;i <= k;i++){ for(int j = 1;j <= length;j++){//如果當(dāng)前剩余歌曲的總時(shí)長(zhǎng)大于單首歌曲的時(shí)長(zhǎng)//那么對(duì)于這首歌有可選和不選兩種選擇//把組合的結(jié)果相加，都算滿(mǎn)足情況if(i >= len[j]){dp[i][j] = (dp[i][j - 1] + dp[i - len[j]][j - 1]) % mod;}//如果當(dāng)前剩余歌曲的總時(shí)長(zhǎng)小于單個(gè)個(gè)的時(shí)長(zhǎng)//代表不能選取這首歌，如果選取總時(shí)長(zhǎng)就肯定會(huì)變長(zhǎng)//不滿(mǎn)足情況else{dp[i][j] = dp[i][j - 1] % mod;}}}cout<<dp[k][length]<<endl;return 0; } 超強(qiáng)干貨來(lái)襲 云風(fēng)專(zhuān)訪(fǎng)：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

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

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