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

const maxn=101;
      maxc=1000000000;
var n,re,e:longint;
    a,l,r:array[1..maxn] of longint;
    m:array[1..maxn,1..maxn] of longint;
    f:array[1..maxn,1..maxn] of longint;

procedure rf;
var i,j,k:longint;
begin
     read(n,e);
     for i:=1 to n do readln(a[i]);
     for i:=2 to n do
         for j:=1 to i-1 do
             l[i]:=l[i]+2*abs(a[i]-a[j]);
     for i:=n-1 downto 1 do
         for j:=n downto i+1 do
             r[i]:=r[i]+2*abs(a[i]-a[j]);
     for i:=1 to n-1 do
         for j:=1 to n do
             for k:=i+1 to j-1 do
                 m[i,j]:=m[i,j]+abs(2*a[k]-a[i]-a[j]);
end;

function min(x,y:longint):longint;
begin
     if x<y then min:=x else min:=y;
end;

procedure pr;
var i,j,k:longint;
begin
     for i:=2 to n do
         for j:=2 to n do
             f[i,j]:=maxc;
     for i:=1 to n do
         f[1,i]:=l[i];
     for i:=2 to n do
         for j:=i to n do
             for k:=1 to j-1 do
                 f[i,j]:=min(f[i,j],f[i-1,k]+m[k,j]);
     for i:=1 to n do
     begin
          for j:=i to n do
              if f[i,j]+r[j]<=e then break;
          if f[i,j]+r[j]<=e then break;
     end;
     re:=i;
     for j:=i to n do
         if f[i,j]+r[j]<e then e:=f[i,j]+r[j];
end;

procedure wf;
begin
     writeln(re,' ',e);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của RR

{
PROG: baric
LANG: PASCAL
ID: invinci3
}
const
  FINP='';
  FOUT='';
  MAXN=101;
  oo=1000000000;
var
  f1,f2:text;
  e,n,kq:longint;
  nn,m:array[1..MAXN] of longint;
  d,sum:array[1..MAXN,1..MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n,e);
  for i:=1 to n do read(f1,m[i]);
end;
procedure init;
var
  i,j,k:longint;
begin
  for i:=1 to n-2 do
  for j:=i+2 to n do
    for k:=i+1 to j-1 do
      inc(sum[i,j],abs(2*m[k]-m[i]-m[j]));
end;
procedure solve;
var
  i,j,k,x:longint;
begin
  for i:=1 to n do
  for j:=2 to n do
    d[i,j]:=oo;
  for k:=1 to n do
    nn[k]:=oo;
  for i:=1 to n do
    begin
      d[i,1]:=0;
      for j:=1 to i-1 do
        inc(d[i,1],2*abs(m[j]-m[i]));
      x:=d[i,1];
      for j:=i+1 to n do inc(x,2*abs(m[j]-m[i]));
      nn[1]:=min(nn[1],x);
    end;
  for i:=2 to n do
  for k:=2 to i do
    begin
      for j:=1 to i-1 do
        d[i,k]:=min(d[i,k],d[j,k-1]+sum[j,i]);
      x:=d[i,k];
      for j:=i+1 to n do inc(x,2*abs(m[j]-m[i]));
      nn[k]:=min(nn[k],x);
    end;
end;
procedure ans;
var
  k:longint;
begin
  for k:=1 to n do
    if nn[k]<=e then
      begin
        writeln(f2,k,' ',nn[k]);
        exit;
      end;
end;
begin
  openF;
  inp;
  init;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define max 1000000000

int TTD(int n)
{
    if(n<0) return -n;
    else return n;
}

int main()
{
   // freopen("BARIC.in","r",stdin);
    int n,E,a[101],f[101][101],d[101][101],KQ = 0,flag=0;
    scanf("%d %d",&n,&E);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    int tt = max;
    for(int i = 1;i<=n;i++)
    {
        f[1][i]=0;
        for(int j = 1;j<=n;j++)
            f[1][i] = f[1][i]+2*TTD(a[j]-a[i]);
        if(f[1][i]<=E)
        { 
                      if(f[1][i]<tt) tt = f[1][i];
                      KQ = 1; }
        //printf("%d ",f[1][i]);
    }
    if(KQ!=0) 
        printf("%d %d",KQ,tt);
    else
    {
    for(int i = 1;i<=n-1;i++)
       for(int j = i+1;j<=n;j++)
       {
           d[i][j] = 0;
           for(int k = j;k<=n;k++)
               d[i][j] = d[i][j]+2*TTD(a[k]-a[j])-2*TTD(a[k]-a[i]);
           for(int k = i+1;k<j;k++)
               d[i][j] = d[i][j]+TTD(2*a[k]-a[i]-a[j])-2*TTD(a[k]-a[i]);
          // printf("%d %d %d\n",i,j,d[i][j]);
       }


        for(int i = 2;i<=n;i++)
        {
            tt=max;
            for(int j = 1;j<=n;j++)
            {
                if(j<i)
                {
                    f[i][j] = max;
                    //continue;
                }
                else
                {
                    f[i][j] = max;
                    for(int k = j-1;k>=i-1;k--)
                    {
                         if(f[i-1][k]+d[k][j]<f[i][j])
                             f[i][j] = f[i-1][k]+d[k][j];
                    }
                }
                if(f[i][j]<=E)
                {
                     if(f[i][j]<tt)
                         tt =f[i][j];
                     KQ = i;}
                   // printf("%d %d %d\n",i,j,f[i][j]);
            }
            if(KQ!=0)
            {
                printf("%d %d",KQ,tt);
                break;
            }
        }
    }
   // getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int n,E;
int cost[102][102],f[102][102];
int a[102];

int main()
{
//    freopen("baric.in","r",stdin);
//    freopen("baric.ou","w",stdout);
    scanf("%d %d", &n, &E);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++)
    {
        cost[0][i] = 0;
        for (int j = 1; j < i; j++) cost[0][i] += 2 * abs(a[j] - a[i]);
    };
    for (int i = 1; i <= n; i++)
    {
        cost[i][n + 1] = 0;
        for (int j = i + 1; j <= n; j++) cost[i][n + 1] += 2 * abs(a[j] - a[i]);
    };            
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++)
      {
          cost[i][j] = 0;
          for (int k = i + 1; k < j; k++) cost[i][j] += abs(2 * a[k] - a[i] - a[j]);
      };

    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) f[i][j] = 1000000000;
    for (int i = 1; i <= n; i++) f[i][1] = cost[0][i];

    int ret = 1,opt = 1000000000;
    while (1)
    {
          opt = 1000000000;
          for (int i = 1; i <= n; i++) opt = min(opt,f[i][ret] + cost[i][n + 1]);
          if (opt <= E) break;
          ret++;
          for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++) f[i][ret] = min(f[i][ret],f[j][ret - 1] + cost[j][i]);
    };
    printf("%d %d\n", ret, opt);
};

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int E, n, rr;
int w[111];
int F[111][111], C[111][111];

bool check(int K) {
    memset( F, 0x1f, sizeof(F));
    F[1][0] = 0;
    for(int t=2;t<=K;++t)
        for(int i=1;i<2+n;++i)
            for(int last=0;last<i;++last)
                F[t][i] <?= F[t-1][last] + C[last][i];
    rr = F[K][n+1];
    return rr <= E;
}

int main() {
    scanf("%d%d", &n, &E);
    for(int i=1;i<=n;++i)
        scanf("%d", &w[i]);
    w[0] = w[n+1] = 0;
    for(int i=0;i<n+2;++i)
        for(int j=i+1;j<n+2;++j)
            for(int k=i+1;k<j;++k)
                if(i==0) C[i][j] += 2 * abs(w[k]-w[j]);
                else if(j==n+1) C[i][j] += 2 * abs(w[k] - w[i]);
                else C[i][j] += abs( 2 * w[k] - w[i] - w[j]);
    int r = n + 2;
    for(int i=1<<8;i>0;i>>=1)
        if(r-i>=3 && check(r-i)) r -= i;
    check(r);
    cout << r - 2 << " " << rr << endl;
    //system("pause");
    return 0;
}