台中女中程式解題系統:b025: 棋盤格城市

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結 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

程式碼:
  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4.   
  5. long long int combi(int n, int k)  
  6. {  
  7.     long long int C[n + 1][k + 1];  
  8.     int i, j;  
  9.   
  10.     for (i = 0; i <= n; i++)  
  11.     {  
  12.         for (j = 0; j <= min(i, k); j++)  
  13.         {  
  14.             if (j == 0 || j == i) // C(n, 0) = C(n, n) = 1  
  15.                 C[i][j] = 1;  
  16.             else // C(n, k) = C(n-1, k-1) + C(n-1, k)  
  17.                 C[i][j] = C[i - 1][j - 1] + C[i - 1][j];  
  18.         }  
  19.     }  
  20.   
  21.     return C[n][k];  
  22. }  
  23.   
  24. int main()  
  25. {  
  26.     int x, y;  
  27.     cin >> x >> y;  
  28.     cout << combi(x+y, x) << endl;  
  29.   
  30.     return 0;  
  31. }  

沒有留言: