R6-1 可重復選擇的組合數問題

【考核知識點】可重復選擇的組合計數

【問題描述】

有n個不同元素（1<=n<20），每個元素可以選多次，一共需要選出k個元素出來（1<=k<20），問有多少種選取的方法數？

例如，n=3，k=2，可以想象成有3種顏色的球（紅、黃、藍），選出2個來，有如下組合。

（紅、紅）

（紅、黃）

（紅、藍）

（黃、黃）

（黃、藍）

（藍、藍）

組合數共計：6種

再例如，n=2，k=6，可以想象成有2種顏色的球（紅、黃），選出6個來，有如下組合。

（6*紅）

（1*黃、5*紅）

（2*黃、4*紅）

（3*黃、3*紅）

（4*黃、2*紅）

（5*黃、1*紅）

（6*黃）

組合數共計：7種

【輸入格式】

n和k。n和k的含義如前述。

【輸出格式】

從n種元素中，可重復選擇挑選k個的組合數。

【提示】

從n種元素中，可重復選擇挑選k個的組合數。假設第i?種元素選xi?個，則此問題轉化為求方程：

x1?+x2?+…+xn?=k?的非負整數解的個數，xi??可以取0。這個方程由于求解非負整數解（xi?可為0），不易分析，可以轉化為：yi?=xi?+1，則求解?y1?+y2?+…+yn?=k+n?的正整數解的個數（yi??不可為0，需要大于0）。

求解?y1?+y2?+…+yn?=k+n?的正整數解的個數，可以想象成這樣一個場景的問題：

有k+n個數字1，排成一排，則問題等價于把這些“1”分成n個部分，有多少種方法？這就相當于在k+n?1個“候選分隔線”（即1和1之間的空檔）中選出n?1個空檔的方法數。即C(k+n?1,n?1)，也是C(k+n?1,k)，因為C(k+n?1,n?1)=C(k+n?1,k)。

函數接口定義：

函數接口定義： long long Combination(int n, int k)

接口參數：?n?和?k?都是傳入的參數。?n?和k的值都不超過20，返回值為long long型，表示從n個中選擇k個的組合數（不講順序）。

測試程序樣例：

#include "stdio.h" #include <iostream> #include "stdlib.h" using namespace std; long long permutation(int n, int k); //計算A(n,k)，n個中選k個的排列數 long long Combination(int n, int k); //計算C(n,k)，n個中選k個的組合數 int main() { int n, k; cin >> n >> k; long long p; //其實，求解C(k+n-1,k)和C(k+n-1,n-1)是相同的，哪個好算算哪個 if(n-1>k) p=Combination(k+n-1,k); else p=Combination(k+n-1,n-1); cout<< p <<endl; return 0; } long long permutation(int n, int k) //計算A(n,k)，n個中選k個的排列數 { long long p=1; for(int i=n; i>=n-k+1; i--) p *= i; return p; } /* 請在這里填寫答案 */

輸入樣例#1：

在這里給出一組輸入。例如：

3 2

輸出樣例#1：

在這里給出相應的輸出。例如：

6

輸入樣例#2：

在這里給出一組輸入。例如：

2 6

輸出樣例#2：

在這里給出相應的輸出。例如：

7

代碼長度限制

16 KB

時間限制

400 ms

內存限制

64 MB

C++ (g++)

long long Combination(int n, int k) {if (k > n) return 0; if (k == 0 || k == n) return 1; k = std::min(k, n - k); long long result = 1;for (int i = 1; i <= k; ++i) {result *= n - (k - i);result /= i;}return result;
}

R6-2 最大連續和

【考察知識點】前綴和、暴力法、分治法、動態規劃等，多種方法皆可。

【問題描述】

給一個長度為n的序列a1?,a2?,…,an?,?每個元素ai?（1<=i<=n），為可正可負可零的整數。

求一個連續子序列ai?,ai+1?,…,aj?，1<=i<=j<=n?，使得連續元素段的和ai?+ai+1?+…+aj?最大。

【輸入格式】

第一行n，表示序列的長度，n<100000。

第二行有n個數，為a1?a2?…an?。

【輸出格式】

最大的連續元素段之和，即?max{ai?+ai+1?+…+aj?}，1<=i<=j<=n?。

【函數接口定義】

函數接口如下： int maxSum(int a[], int n)；

【裁判測試程序】

#include "stdio.h" #include <iostream> #include "stdlib.h" using namespace std; int maxSum(int a[], int n); int main() { int n, a[100000]; cin>>n; if(n>0) { for(int i=1;i<=n;i++) cin>>a[i]; } else return 1; int mxs=maxSum(a, n); cout<<mxs<<endl; return 0; } /* 請在這里填寫答案 */

【輸入樣例】

在這里給出一組輸入。例如：

10
-2 3 -3 2 4 8 6 1 -2 -4

【輸出樣例】

在這里給出相應的輸出。例如：

21

代碼長度限制

16 KB

時間限制

400 ms

內存限制

64 MB

#include <climits> int maxSum(int a[], int n) {int maxSoFar = INT_MIN; int maxEndingHere = 0;  for (int i = 0; i < n; i++) {maxEndingHere += a[i];if (maxSoFar < maxEndingHere)maxSoFar = maxEndingHere;if (maxEndingHere < 0)maxEndingHere = 0;}return maxSoFar;
}

?