Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define N 2020
#define oo 1000111222
using namespace std;

int n,m,a[N],f[N],l[N][N],r[N][N],pos[N],prev[N];
pair <int,int> b[N];

int uniqueSeq(pair <int,int> b[],int cnt[])
{
    int m=1;
    pos[b[1].second]=1; cnt[1]++;
    for (int i=2;i<=n;i++)
    {
        if (b[i].first>b[m].first) b[++m]=b[i], prev[b[i].second]=0;
        else prev[b[i].second]=b[i-1].second;
        pos[b[i].second]=m; cnt[m]++; 
    }
    return m;
}

void initToI(int i,int m,int _L[],int _R[],int _cnt[])
{
    int L[N],R[N],cnt[N];
    for (int j=0;j<=m+1;j++) L[j]=_L[j], R[j]=_R[j], cnt[j]=_cnt[j];
    for (int j=1;j<=i;j++)
    {
        int x=pos[j];
        l[i][j]=L[x]; r[i][j]=R[x]; 
        if (!--cnt[x]) L[R[x]]=L[x], R[L[x]]=R[x];
    }
}

void init()
{
    int cnt[N]={0},L[N],R[N];
    for (int i=1;i<=n;i++) b[i]=make_pair(a[i],i);
    sort(b+1,b+n+1);
    m=uniqueSeq(b,cnt);
    for (int i=0;i<=m+1;i++) L[i]=i-1, R[i]=i+1;
    for (int i=n;i;i--)
    {
        initToI(i,m,L,R,cnt);
        int x=pos[i];
        if (!--cnt[x]) L[R[x]]=L[x], R[L[x]]=R[x];
    }
}

void update(int &minDif,int &num,int dif)
{
    if (dif==minDif) num++;
    else
        if (dif<minDif) minDif=dif, num=1;
}

void solve()
{
    for (int i=1;i<=n;i++)
    {
        f[i]=f[i-1]+1; 
        int border=prev[i],minDif=oo,num=0;
        for (int j=i-1;j>border;j--)
        {
            int L=l[i][j],R=r[i][j];
            if (L) update(minDif,num,a[j]-b[L].first);
            if (R<=m) update(minDif,num,b[R].first-a[j]);
            if (num==i-j) f[i]=min(f[i],f[j-1]+1);
            border=max(border,prev[j]);
        }
    }
}

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    init();
    solve();
    cout << f[n] << endl;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 2020;
const int oo = 1000000009;
using namespace std;
int a[N], lim[N], F[N];
int n;
map<int, int> M;

int gcd(int a, int b) {while (b) a %= b, swap(a, b); return a;}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        if (M.count(a[i]) != 0) lim[i] = M[a[i]];
        M[a[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        F[i] = F[i - 1] + 1;
        int g = 0, mi = a[i], ma = a[i], l = lim[i];
        for(int j = i - 1; j; j--) {
            mi = min(mi, a[j]); ma = max(ma, a[j]);
            g = gcd(g, abs(a[j + 1] - a[j])); l = max(l, lim[j]);
            if (j == l) break;
            int d = ma - mi, c = i - j;
            if (d == g * c) F[i] = min(F[i], F[j - 1] + 1);
        }
    }
    printf("%d", F[n]);
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) { cout << #x << " = "; cout << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
const int BUFSIZE = (1<<12) + 17;
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp && !REACHEOF) { \
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 2011;
const int oo = 1000111000;

int n, a[MN], max_lower[MN][MN], min_greater[MN][MN], good[MN][MN], f[MN];

int main() {
    while (scanf("%d", &n) == 1) {
        FOR(i,1,n) scanf("%d", &a[i]);
        FOR(j,1,n) {
            max_lower[j][j] = -oo;
            min_greater[j][j] = oo;
            FORD(i,j-1,1) {
                max_lower[i][j] = max_lower[i+1][j];
                min_greater[i][j] = min_greater[i+1][j];

                if (a[i] >= a[j]) min_greater[i][j] = min(a[i], min_greater[i][j]);
                if (a[i] < a[j]) max_lower[i][j] = max(a[i], max_lower[i][j]);
            }
        }

        f[n+1] = 0;
        FORD(i,n,1) {
            f[i] = f[i+1] + 1;

            int mind = oo, cnt = 0;
            FOR(j,i+1,n) {
                if (min_greater[i][j] - a[j] < mind) {
                    mind = min_greater[i][j] - a[j];
                    cnt = 1;
                }
                else if (min_greater[i][j] - a[j] == mind) {
                    ++cnt;
                }

                if (a[j] - max_lower[i][j] < mind) {
                    mind = a[j] - max_lower[i][j];
                    cnt = 1;
                }
                else if (a[j] - max_lower[i][j] == mind) {
                    ++cnt;
                }

                if (mind && cnt == j - i) f[i] = min(f[i], f[j+1] + 1);
            }
        }
        cout << f[1] << endl;
    }
    return 0;
}

Code mẫu của hieult

#pragma comment(linker, "/STACK:16777216")

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 2002
#define base 1000000000
#define modunlo 111539786
#define oo 2000000002
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define ull unsigned long long

double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

typedef long long int64;
int a[maxn],next[maxn][maxn],previous[maxn][maxn],f[maxn];
int n,t, MIN, MAX, subMIN;

int main(){
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        next[i][i] = previous[i][i] = -1;
    }
    for(int add = 1; add < n; add++){
        for(int i = 1; i <= n - add; i++){
            if(a[i] == a[i + add]) {
                    next[i][i + add] = i;
                    previous[i][i + add] = i;
            }
            else if(next[i + 1][i + add] == -1){
                if(a[i] > a[i + add]){
                    next[i][i + add] = i;
                    previous[i][i + add] =  previous[i + 1][i + add];
                }
                else {
                    next[i][i + add] = -1;
                    t = previous[i + 1][i + add];
                    if(t == -1 || a[i] > a[t]) previous[i][i + add] = i;
                    else previous[i][i + add] = t;
                }
            }
            else if(previous[i + 1][i + add] == -1){
                if(a[i] < a[i + add]){
                    previous[i][i + add] = i;
                    next[i][i + add] = next[i + 1][i + add];
                }
                else{
                    previous[i][i + add] = -1;
                    t = next[i + 1][i + add];
                    if( t == -1 || a[i] < a[t]) next[i][i + add] = i;
                    else next[i][i + add] = t;
                }
            }
            else{
                if(a[i] >= a[i + add] && a[i] <= a[next[i + 1][i + add]]){
                    next[i][i + add] = i;
                    previous[i][i + add] = previous[i + 1][i + add];
                }
                else if(a[i] <= a[i + add] && a[i] >= a[previous[i + 1][i + add]]){
                    previous[i][i + add] = i;
                    next[i][i + add] = next[i + 1][i + add];
                }
                else{
                    next[i][i + add] = next[i + 1][i + add];
                    previous[i][i + add] = previous[i + 1][i + add];
                }
            }
        }
    }

    f[0] = 0;
    for(int i = 1; i <= n; i++) f[i] = oo;

    for(int i = 1; i <= n; i++){
        MIN = a[i], MAX = a[i], subMIN = oo;
        f[i] = min(f[i], f[i - 1] + 1);
        for(int j = i + 1; j <= n; j++){
            MIN = min(MIN, a[j]);
            MAX = max(MAX, a[j]);
            if(previous[i][j] > 0) subMIN = min(subMIN, a[j] - a[previous[i][j]]);
            if(next[i][j] > 0) subMIN = min(subMIN, a[next[i][j]] - a[j]);
            if((long long)subMIN * (j - i) == MAX - MIN && (MAX - MIN) > 0){
                f[j] = min(f[j], f[i - 1] + 1);
            }
        }
    }
    printf("%d",f[n]);
}