POJ 1306 - Combinations

http://poj.org/problem?id=1306

概要

C(n,m) を計算して答える

制約

• 5 <= m <= n <= 100

解法

DP 的に C(n,m) を予め計算しておいてから答える．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7   static const int N = 100, M = 100;
 8 
 9   vector<vector<int> > c(N+1, vector<int>(M+1, 1));
10   for (int i = 2; i <= N; i++) {
11     for (int j = 1; j < i; j++) {
12       c[i][j] = c[i-1][j] + c[i-1][j-1];
13     }
14   }
15 
16   int n, m;
17   while (cin >> n >> m && !(n == 0 && m == 0)) {
18     cout << n << " things taken " << m << " at a time is " << c[n][m] << " exactly." << endl;
19   }
20 
21   return 0;
22 }