fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 505;
  5. const int mod = 1e9+7;
  6. typedef pair<int, int> ii;
  7. #define fi first
  8. #define se second
  9. #define read(_a, n) for(int i = 1; i <= n; i++) cin >> _a[i]
  10. #define For(i, _a, _b) for(int i = _a; i <= _b; i++)
  11. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  12. #define File(_x,_y) if (fopen(_x, "r")) freopen(_x, "r", stdin)//,freopen(_y, "w", stdout)
  13. #define file "main"
  14. #define bit(x, i) ((x >> i) & 1)
  15. #define bat(x, i) (x  (1 << i))
  16.  
  17. int n, dp[maxn][maxn], a[maxn], xmin[maxn][maxn], num[maxn][maxn][maxn];
  18. int f[maxn];
  19. char ok[maxn][maxn];
  20. bool dd[maxn];
  21.  
  22. void Make_seq()
  23. {
  24.     for (int i = 1; i <= n; i++)
  25.     {
  26.         memset(dd, 0, sizeof(dd));
  27.         int xmax = -1, same = 0;
  28.         xmin[i][i - 1] = 501;
  29.         for (int j = i; j <= n; j++)
  30.         {
  31.             if (dd[a[j]]) same = 1;
  32.             dd[a[j]] = 1;
  33.             xmin[i][j] = min(xmin[i][j - 1], a[j]);
  34.             xmax = max(xmax, a[j]);
  35.             if (same)
  36.             {
  37.                 ok[i][j] = 0;
  38.                 continue;
  39.             }
  40.             if (xmax == (j - i + 1)) ok[i][j] = 2;
  41.             else ok[i][j] = 1;
  42.         }
  43.     }
  44.  
  45.     for (int i = 1; i <= n; i++)
  46.         for (int j = i; j <= n; j++)
  47.             if (ok[i][j] == 1)
  48.             {
  49.                 memset(dd, 0, sizeof(dd));
  50.                 for (int k = i; k <= j; k++) dd[a[k]] = 1;
  51.                 num[i][j][501] = 0;
  52.                 for (int k = 500; k >= 0; k--)
  53.                     num[i][j][k] = num[i][j][k + 1] + dd[k];
  54.             }
  55. }
  56.  
  57. int32_t main()
  58. {
  59.     fastIO
  60.     cin >> n;
  61.     read(a, n);
  62.  
  63.     Make_seq();
  64.  
  65.     memset(dp, 60, sizeof(dp));
  66.     for (int i = n; i; i--)
  67.     {
  68.         dp[i][i] = 0;
  69.         for (int j = i + 1; j <= n; j++)
  70.         {
  71.             if (ok[i][j] > 0)
  72.             {
  73.                 for (int k = i; k < j; k++)
  74.                 {
  75.                     int t = dp[i][k] + dp[k + 1][j];
  76.                     if (xmin[i][k] < xmin[k + 1][j])
  77.                         t += num[i][k][xmin[k + 1][j]] + j - k;
  78.                     else
  79.                         t += num[k + 1][j][xmin[i][k]] + k - i + 1;
  80.                     dp[i][j] = min(dp[i][j], t);
  81.                 }
  82.             }
  83.         }
  84.     }
  85.  
  86.     memset(f, 60, sizeof(f));
  87.     f[0] = 0;
  88.     for (int i = 1; i <= n; i++)
  89.         for (int j = 0; j < i; j++)
  90.             if (ok[j + 1][i] == 2)
  91.                 f[i] = min(f[i], f[j] + dp[j + 1][i]);
  92.  
  93.     if (f[n] >= 1e9) cout << "Impossible";
  94.     else cout << f[n];
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 21472KB
comments (?)
stdin 
7
1 2 3 2 4 1 3
stdout 
7
https://ideone.com/ylqS6z
DOLLS
language:
C++14 (gcc 8.3)
created:
11 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!