fork download
copy 
  1. /*
  2. #dynamic programming
  3. */
  4. /*
  5. f(m, n) = số dãy không giảm x[1...m] có tổng bằng n và max <= k
  6. Nếu x[1] = 0: Số lượng: f(m - 1, n);
  7. Nếu x[1] > 0:
  8.              ++
  9.             +++
  10.           +++++
  11.        ++++++++
  12.       *******
  13.   Giảm x[1...m] mỗi số đi 1 đơn vị (bỏ hàng *)
  14.   Phần còn lại (dấu +) biểu diễn một dãy
  15.   . Có m phần tử,
  16.   . Tổng bằng n - m
  17.   . Max < k
  18.   Số lượng = f(m, n - m) - (Số dãy trong f(m, n - m) có max = x[m] = k)
  19.            = f(m, n - m) - f(m - 1, n - m - k)
  20. *: Dùng 2 vector 1D để tiết kiệm bộ nhớ và tăng tốc.
  21. */
  22. #define taskname "GAME"
  23. #include <iostream>
  24. #include <cstdio>
  25. #include <algorithm>
  26. #include <vector>
  27. using namespace std;
  28. const int maxMNK = 5001;
  29. const int MOD = 1e9 + 7;
  30. int n, m, k;
  31. vector<int> f, g;
  32.  
  33. int main()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.     freopen(taskname".INP", "r", stdin);
  38.     freopen(taskname".OUT", "w", stdout);
  39.     cin >> n >> m >> k;
  40.     f.resize(n + 1, 0); g.resize(n + 1);
  41.     f[0] = 1;
  42.     for (int i = 1; i <= m; ++i)
  43.     {
  44.         for (int j = 0; j <= n; ++j)
  45.         {
  46.             g[j] = f[j];
  47.             if (j >= i)
  48.             {
  49.                 g[j] = (g[j] + g[j - i]) % MOD;
  50.                 if (j - i - k >= 0)
  51.                     g[j] = (g[j] - f[j - i - k]) % MOD;
  52.             }
  53.         }
  54.         f.swap(g);
  55.     }
  56.     cout << (f[n] + MOD) % MOD;
  57. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Bfm2nC
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!