題意：一個(gè)人N門課程的總成績(jī)?yōu)門，每門課程的最低成績(jī)?yōu)镻，求一共有多少種可能的分配方法。

題解：可以先求出超出的部分 T = T - n*p；剩余的相當(dāng)于n個(gè)里面每個(gè)科目放0，1分等。

這題我只懂了遞推，不懂組合數(shù)學(xué)，看來太弱了

dp[i][j] = dp[i-1][0] + dp[i-1][1] +......+d[[i-1][j];表示前i個(gè)盒子放j個(gè)球的方法

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; LL dp[80][80]; int main(){int t,n,T,p;cin >> t;while(t--){cin >> n >> T >> p;T = T - n * p;memset(dp,0,sizeof(dp));for(int i = 0;i <= n;i++)dp[i][0] = 1;for(int i = 1;i <= n;i++){for(int j = 1;j <= T;j++){for(int k = 0;k <= j;k++){dp[i][j] += dp[i-1][k];}}}cout << dp[n][T] << endl;} }
組合數(shù)學(xué)

把T分分成T份放入到n個(gè)科目中，相當(dāng)于把T個(gè)球放到n個(gè)盤子中，用多少種方法？（求大神解釋|隔板法俺不懂啊）

#include <cstdio> typedef long long LL;LL C(LL n, LL k) {if(n - k < k) k = n - k;LL ans = 1;for(int i = 1; i <= k; i++)ans = ans * (n - i + 1) / i;return ans; }int main() {int cas;LL n, t, p;scanf("%d", &cas);while(cas--) {scanf("%lld%lld%lld", &n, &t, &p);t = t - n * p;LL ans = C(n + t - 1, n - 1);printf("%lld\n", ans);}return 0; }

隔板法：

將20個(gè)大小形狀完全相同的小球放入3個(gè)不同的盒子，允許有盒子為空，但球必須放完，有多少種不同的方法？ 分析：本題中的小球大小形狀完全相同，故這些小球沒有區(qū)別，問題等價(jià)于將小球分成三組，允許有若干組無元素，用隔板法. 解析：將20個(gè)小球分成三組需要兩塊隔板，因?yàn)樵试S有盒子為空，不符合隔板法的原理，那就人為的再加上3個(gè)小球，保證每個(gè)盒子都至少分到一個(gè)小球，那就符合隔板法的要求了（分完后，再在每組中各去掉一個(gè)小球，即滿足了題設(shè)的要求）。然后就變成待分小球總數(shù)為23個(gè)，球中間有22個(gè)空檔，需要在這22個(gè)空檔里加入2個(gè)隔板來分隔為3份，共有C（22，2）=231種不同的方法. 點(diǎn)評(píng)：對(duì)n件相同物品（或名額）分給m個(gè)人（或位置），允許若干個(gè)人（或位置）為空的問題,可以看成將這n件物品分成m組，允許若干組為空的問題.將n件物品分成m組，需要m-1塊隔板，將這n件物品和m-1塊隔板排成一排，占n+m-1位置，從這n+m-1個(gè)位置中選m-1個(gè)位置放隔板，因隔板無差別，故隔板之間無序，是組合問題，故隔板有Cn+m-1 m-1種不同的方法，再將物品放入其余位置，因物品相同無差別，故物品之間無順序，是組合問題，只有1種放法，根據(jù)分步計(jì)數(shù)原理，共有Cn+m-1 m-1×1=Cn+m-1 m-1種排法 例2：有廣西橘子，煙臺(tái)蘋果，萊陽梨若干，從中隨意取出四個(gè)，問共有多少種不同取法？ 問題等價(jià)于有四個(gè)水果籃，將其分為三組向里面加入不同水果，且允許籃子為空 分為三組需要2個(gè)隔板，將水果籃與隔板并排 ，隔板共有4+2個(gè)放置位置，故有C（4+2），2個(gè)選擇， 即15種。[1] 將20個(gè)優(yōu)秀學(xué)生名額分給18個(gè)班，每班至少1個(gè)名額，有多少種不同的分配方法？ 分析：本題是名額分配問題，用隔板法. 解析：將20個(gè)名額分配給18個(gè)班，每班至少1個(gè)名額，相當(dāng)于將20個(gè)相同的小球分成18組，每組至少1個(gè)，將20個(gè)相同的小球分成18組，需要17塊隔板，先將20個(gè)小球排成一排，因小球相同，故小球之間無順序，是組合，只有1種排法，再在20個(gè)小球之間的19個(gè)空檔中，選取17個(gè)位置放隔板，因隔板無差別，故隔板之間無序，是組合問題，故隔板有C19 17種不同的放法，根據(jù)分步計(jì)數(shù)原理，共有C19 17種不同的方法，因17塊隔板將20個(gè)小球分成18組，從左到右可以看成每班所得的名額數(shù)，每一種隔板與小球的排法對(duì)應(yīng)于一種分法，故有Cm-1 n-1種分法.

總結(jié)

以上是生活随笔為你收集整理的UVA 10910 Marks Distribution（组合数学 或 递推）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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