fork download 
  1. // #pragma GCC optimize("O3,unroll-loops")
  2. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // __builtin_popcount
  6. // __builtin_ctz
  7. // #define int long long
  8. #define pii pair<int, int>
  9. #define duoble long double
  10. #define endl '\n'
  11. #define fi first
  12. #define se second
  13. #define mapa make_pair
  14. #define pushb push_back
  15. #define pushf push_front
  16. #define popb pop_back
  17. #define popf pop_front
  18. #define o_ ordered_
  19. #define ins insert
  20. #define era erase
  21. #define pqueue priority_queue
  22. #define minele min_element
  23. #define maxele max_element
  24. #define lb lower_bound // >=
  25. #define ub upper_bound // >
  26. #define debug cout << "NO ERROR", exit(0)
  27. #define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28. #define MASK(i) (1LL << (i))
  29. #define BIT(x, i) (((x) >> (i)) & 1)
  30. #define ALL(v) v.begin(), v.end()
  31. #define SZ(v) (int)v.size()
  32. #define sqr(x) ((x) * (x))
  33.  
  34. template<class X, class Y>
  35.     bool minimize(X &x, const Y &y) {
  36.         if (x > y) {
  37.             x = y;
  38.             return true;
  39.         }
  40.         return false;
  41.     }
  42. template<class X, class Y>
  43.     bool maximize(X &x, const Y &y) {
  44.         if (x < y) {
  45.             x = y;
  46.             return true;
  47.         }
  48.         return false;
  49.     }
  50.  
  51. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  52.  
  53. int Rand(const int &l, const int &r) {
  54.     assert(l <= r);
  55.     int sz = (r - l + 1);
  56.     return l + rd() % sz;
  57. }
  58.  
  59.  
  60. const int MOD = 1e9 + 7; //998244353;
  61. const int LOG = 18;
  62. const int INF = 1e9 + 7;
  63. const int d4x[4] = {-1, 1, 0, 0};
  64. const int d4y[4] = {0, 0, 1, -1};
  65. const char c4[4] = {'U', 'D', 'R', 'L'};
  66. const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  67. const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  68.  
  69.  
  70. const int LimN = 5e3 + 5;
  71.  
  72. int n, k, a[LimN], f[LimN][LimN], pref[LimN], pre[LimN];
  73.  
  74. void compress() {
  75.     vector<int> comp;
  76.     for (int i = 1; i <= n; i++) {
  77.         comp.pushb(a[i]);
  78.     }
  79.     sort(ALL(comp));
  80.     comp.resize(unique(ALL(comp)) - comp.begin());
  81.     for (int i = 1; i <= n; i++) {
  82.         a[i] = lb(ALL(comp), a[i]) - comp.begin() + 1;
  83.     }
  84. }
  85.  
  86.  
  87. void solve() {
  88.  
  89.     cin >> n >> k;
  90.     for (int i = 1; i <= n; i++) cin >> a[i];
  91.  
  92.     compress();
  93.     memset(f, 0x3f, sizeof f);
  94.     memset(pref, 0x3f, sizeof pref);
  95.     memset(pre, -1, sizeof pre);
  96.  
  97.     // for (int i = 1; i <= n; i++) cout << a[i] << " " << pre[a[i]] << endl;
  98.  
  99.     pref[0] = 0;
  100.     int ans = INF;
  101.     for (int i = 1; i <= n; i++) {
  102.         for (int j = 1; j <= k + 1; j++) {
  103.             f[i][j] = pref[j - 1] + i - 1;
  104.             if (pre[a[i]] != -1) minimize(f[i][j], f[pre[a[i]]][j] + (i - pre[a[i]] - 1));
  105.         }
  106.         for (int j = 1; j <= k + 1; j++) {
  107.             minimize(pref[j], f[i][j] - i);
  108.             minimize(ans, f[i][j] + n - i);
  109.         }
  110.         pre[a[i]] = i;
  111.     }
  112.     cout << ans << endl;
  113.  
  114.  
  115.  
  116.  
  117. }
  118.  
  119.  
  120.  
  121.  
  122.  
  123. signed main() {
  124.  
  125.     #ifndef ONLINE_JUDGE
  126.     freopen("ab.inp", "r", stdin);
  127.     freopen("ab.out", "w", stdout);
  128.     #else
  129.     // freopen("task.inp", "r", stdin);
  130.     // freopen("task.out", "w", stdout);
  131.     #endif
  132.     FAST;
  133.     bool TestCase = 0;
  134.     int NumTest = 1;
  135.     cin >> NumTest;
  136.     for (int i = 1; i <= NumTest; i++) {
  137.         if (TestCase) cout << "Case" << " " << i << ": ";
  138.         solve();
  139.     }
  140.  
  141. }
  142.  
Success #stdin #stdout 0.02s 101368KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000007
https://ideone.com/wOj3zY
language:
C++14 (gcc 8.3)
created:
2 days 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!