fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define nn "\n"
  6. const int INF = 1e18;
  7. const int mod = 1e9+7;
  8. const int N = 100000 + 5;
  9.  
  10. int x;
  11. int dp[N];        // số cách
  12. int f[N];         // số lượng min
  13. int trace[N];     // truy vết
  14. vector<int> c;
  15.  
  16. signed main() {
  17.     ios::sync_with_stdio(0);
  18.     cin.tie(0);
  19.  
  20.     cin >> x;
  21.  
  22.     // sinh các số chính phương
  23.     for (int i = 1; i * i <= x; i++) {
  24.         c.push_back(i * i);
  25.     }
  26.  
  27.     // khởi tạo
  28.     dp[0] = 1;
  29.     for (int i = 1; i <= x; i++) {
  30.         f[i] = INF;
  31.     }
  32.  
  33.     // DP
  34.     for (int i = 1; i <= x; i++) {
  35.         for (int k : c) {
  36.             if (k > i) break;
  37.  
  38.             // đếm số cách
  39.             dp[i] = (dp[i] + dp[i - k]) % mod;
  40.  
  41.             // tối ưu số lượng + truy vết
  42.             if (f[i] > f[i - k] + 1) {
  43.                 f[i] = f[i - k] + 1;
  44.                 trace[i] = k;
  45.             }
  46.         }
  47.     }
  48.  
  49.     cout << dp[x] << " " << f[x] << nn;
  50.  
  51.     // truy vết
  52.     vector<int> ans;
  53.     int cur = x;
  54.     while (cur > 0) {
  55.         ans.push_back(trace[cur]);
  56.         cur -= trace[cur];
  57.     }
  58.  
  59.     // in các số chính phương dùng
  60.     for (int v : ans) cout << v << " ";
  61.     cout << nn;
  62.  
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5668KB
comments (?)
stdin 
19
stdout 
354 3
1 9 9
https://ideone.com/CyD19s
language:
C++14 (gcc 8.3)
created:
19 hours 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!