#include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> using namespace std; typedef long long ll; const int N = 42; struct hsh { ll operator() (const vector <int> &a) const { ll h = 0; for (int x : a) h = h * 40 + x; return h; } }; unordered_map <vector <int>, pair <int, ll>, hsh> mp[N][N]; int main() { #ifdef iq freopen("a.in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector <int> perm(n); for (int i = 0; i < n; i++) { cin >> perm[i]; } vector <int> arr(n); mp[0][0][arr] = make_pair(0, 1ll); auto relax = [&] (int i, int j, vector <int> t, pair <int, ll> cur) { if (!mp[i][j].count(t)) { mp[i][j][t] = cur; } else { if (mp[i][j][t].first < cur.first) { return; } if (mp[i][j][t].first == cur.first) { mp[i][j][t].second += cur.second; } else { mp[i][j][t] = cur; } } }; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { for (auto c : mp[i][j]) { auto go = c.first; auto p = c.second; p.first += go[i]; go[i] = 0; relax(i + 1, j, go, c.second); for (int j = i + 1; j < n; j++) if (perm[j] < perm[i]) go[j]++; relax(i + 1, j + 1, go, p); } } } for (int i = 1; i <= n; i++) { cout << mp[n][i][arr].first << ' ' << mp[n][i][arr].second << '\n'; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> using namespace std; typedef long long ll; const int N = 42; struct hsh { ll operator() (const vector <int> &a) const { ll h = 0; for (int x : a) h = h * 40 + x; return h; } }; unordered_map <vector <int>, pair <int, ll>, hsh> mp[N][N]; int main() { #ifdef iq freopen("a.in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector <int> perm(n); for (int i = 0; i < n; i++) { cin >> perm[i]; } vector <int> arr(n); mp[0][0][arr] = make_pair(0, 1ll); auto relax = [&] (int i, int j, vector <int> t, pair <int, ll> cur) { if (!mp[i][j].count(t)) { mp[i][j][t] = cur; } else { if (mp[i][j][t].first < cur.first) { return; } if (mp[i][j][t].first == cur.first) { mp[i][j][t].second += cur.second; } else { mp[i][j][t] = cur; } } }; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { for (auto c : mp[i][j]) { auto go = c.first; auto p = c.second; p.first += go[i]; go[i] = 0; relax(i + 1, j, go, c.second); for (int j = i + 1; j < n; j++) if (perm[j] < perm[i]) go[j]++; relax(i + 1, j + 1, go, p); } } } for (int i = 1; i <= n; i++) { cout << mp[n][i][arr].first << ' ' << mp[n][i][arr].second << '\n'; } } |