fork(1) download
copy 
  1. //
  2. // Created by Naman Bhalla on 29/09/19.
  3. //
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. int a[101];
  10.  
  11. int dp[101][101];
  12. int mm[101][101];
  13. int ct[1001];
  14.  
  15. int main(){
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(NULL);
  18.     cout.tie(NULL);
  19.  
  20.     int t;
  21.     cin >> t;
  22.  
  23.     for(int cs = 1; cs <= t; ++cs){
  24.         cout << "Case #" << cs << ": ";
  25.         memset(dp, 0, sizeof dp);
  26.         memset(mm, 0, sizeof mm);
  27.  
  28.         int n, k;
  29.         cin >> n >> k;
  30.  
  31.         for(int i = 1; i <= n; ++i){
  32.             cin >> a[i];
  33.         }
  34.  
  35.         for(int i = 1; i <= n; ++i){
  36.             memset(ct, 0, sizeof ct);
  37.             int mmc = 0;
  38.             for(int j = i; j <= n; ++j){
  39.                 ++ct[a[j]];
  40.                 if(ct[a[j]] > mmc){
  41.                     mmc = ct[a[j]];
  42.                 }
  43.                 mm[i][j] = mmc;
  44.             }
  45.         }
  46.  
  47.         for(int i = 0; i <= n; ++i){
  48.             for(int j = 0; j <= n; ++j){
  49.                 dp[i][j] = INT_MAX;
  50.             }
  51.         }
  52.  
  53.         dp[0][1] = 0;
  54.         for(int i = 1; i <= n; ++i){
  55.             dp[i][1] = i - mm[1][i];
  56.         }
  57.  
  58.  
  59.         for(int i = 1; i <= n; ++i){
  60.             for(int j = 2; j <= k + 1; ++j){
  61.                 for(int l = i; l >= 1; --l){
  62.                     if(dp[l - 1][j - 1] != INT_MAX)
  63.                         dp[i][j] = min(dp[i][j], (i - l + 1 - mm[l][i]) + dp[l - 1][j - 1]);
  64.                 }
  65.             }
  66.         }
  67.  
  68.         int ans = INT_MAX;
  69.  
  70.         for(int j = 1; j <= k + 1; ++j){
  71.             ans = min(ans, dp[n][j]);
  72.         }
  73.  
  74.         cout << ans << "\n";
  75.     }
  76.  
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
4
8 2
300 100 300 300 200 100 800 500
5 3
100 100 100 100 3
7 3
10 20 40 10 10 30 30
10 2
30 30 60 60 90 90 60 60 30 30
stdout
copy 
Case #1: 3
Case #2: 0
Case #3: 1
Case #4: 2
https://ideone.com/i80LgQ
language:
C++14 (gcc 8.3)
created:
5 years 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!