題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b025。
分析完題目後,會得到這是 combination 問題:
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
- #include <iostream>
- using namespace std;
- long long int combi(int n, int k)
- {
- long long int C[n + 1][k + 1];
- int i, j;
- for (i = 0; i <= n; i++)
- {
- for (j = 0; j <= min(i, k); j++)
- {
- if (j == 0 || j == i) // C(n, 0) = C(n, n) = 1
- C[i][j] = 1;
- else // C(n, k) = C(n-1, k-1) + C(n-1, k)
- C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
- }
- }
- return C[n][k];
- }
- int main()
- {
- int x, y;
- cin >> x >> y;
- cout << combi(x+y, x) << endl;
- return 0;
- }
沒有留言:
張貼留言