fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define maxn 505
  7. #define FOR(i , a , b) for(int i = a ; i <= b; i++)
  8. #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9.  
  10. int a[maxn] , dp[maxn][maxn] , f[maxn];
  11.  
  12. int main(){
  13.     FAST;
  14.     int n;
  15.     cin >> n;
  16.     FOR(i , 1 , n) cin >> a[i];
  17.     // goi dp[l][r] la gia tri x + 1 sau khi gop 
  18.     // dp[l][l] = a[l]
  19.     FOR(i , 1 , n) dp[i][i] = a[i];
  20.     FOR(len , 2 , n){
  21.         for(int i = 1 ; i + len - 1 <= n ; i++){
  22.             int j = i + len - 1;
  23.             dp[i][j] = 0;
  24.  
  25.             FOR(k , i , j - 1){
  26.                 if(dp[i][k] > 0 && dp[i][k] == dp[k + 1][j]){
  27.                     dp[i][j] = dp[i][k] + 1;
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     // goi f[i] la so doan toi thieu co the chia khi xet 1..i
  33.     FOR(i , 0 , n) f[i] = INT_MAX;
  34.     f[0] = 0;
  35.     FOR(i , 1 , n){
  36.         FOR(j , 1 , i){
  37.             if(dp[j][i] > 0){
  38.                 f[i] = min(f[i] , f[j - 1] + 1);
  39.             }
  40.         }
  41.     }
  42.     cout << f[n];
  43. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
5
4 3 2 2 3
stdout 
2
https://ideone.com/kBtcoM
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!