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 fi='';
      fo='';
      maxn=2000;
var n:longint;
    a:array[0..maxn] of longint;
    f,k:array[1..maxn,1..maxn] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     a[0]:=0;
     for i:=1 to n do
     begin
          readln(t);
          a[i]:=a[i-1]+t;
     end;
     close(input);
end;

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

procedure pr;
var i,j,l,t,u:longint;
begin
     for i:=1 to n do k[i,i]:=i;
     for l:=2 to n do
         for i:=1 to n-l+1 do
         begin
              j:=i+l-1;
              for t:=k[i,j-1] to k[i+1,j] do
              begin
                   if t=i then continue;
                   u:=min(f[i,t-1]+a[t-1]-a[i-1],f[t,j]+a[j]-a[t-1]);
                   if u>f[i,j] then
                   begin
                        f[i,j]:=u;
                        k[i,j]:=t;
                   end;
              end;
         end;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(f[1,n]);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 2020;

using namespace std;
int F[N][N], P[N][N];
int n, s[N], a[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    for(int i = 0; i <= n + 1; i++) P[i][i] = i;
    for(int len = 1; len <= n; len++)
    for(int i = 1; i <= n - len; i++)  {
        int j = i + len;
        for(int k = max(i, P[i][j - 1]); k <= P[i + 1][j] && k < j; k++) {
            int t = min(s[k] - s[i - 1] + F[i][k], s[j] - s[k] + F[k + 1][j]);
            if (F[i][j] < t) {
                F[i][j] = t; P[i][j] = k;
            }
        }
    }
    cout << F[1][n];
    return 0;
}

Code mẫu của RR

//Written by RR
{$R+,Q+}
{$Mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       2011;

var
  f1,f2         :       text;
  f,g           :       array[1..MAXN,1..MAXN] of longint;
  s             :       array[0..MAXN] of longint;
  n             :       longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        begin
          read(f1,s[i]);
          inc(s[i],s[i-1]);
        end;
    end;

procedure solve;
    var
      i,j,x,k:longint;
    begin
      for i:=n downto 1 do
        begin
          g[i,i]:=i;
          for j:=i+1 to n do
            begin
              for k:=g[i,j-1] to g[i+1,j] do
                if (i<k) then
                  begin
                    x:=min(f[i,k-1]+s[k-1]-s[i-1],f[k][j]+s[j]-s[k-1]);
                    if x>f[i,j] then
                      begin
                        f[i,j]:=x;
                        g[i,j]:=k;
                      end;
                  end;
            end;
        end;
      writeln(f2,f[1,n]);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long min(long x,long y)
  {
  if(x<y) return x;
  else return y;
  }
main()
{
long n,a[2001],cat[2001][2001],f[2001][2001],tong[2001][2001],max;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
  scanf("%ld",&a[i]);
for(long i=1;i<=n;i++)
  for(long j=i;j<=n;j++)
    {
    if(i==j)
      tong[i][j]=a[i];
    else tong[i][j]=tong[i][j-1]+a[j];
    //printf("%ld\n",tong[i][j]);
    }    
for(long i=1;i<=n;i++)
  f[i][i]=0;
for(long i=1;i<=n-1;i++)
  {
  f[i][i+1]=min(a[i],a[i+1]);
  cat[i][i+1]=i;
  //printf("%ld\n",f[i][i+1]);
  }
for(long i=3;i<=n;i++)
  for(long j=1;j<=n-i+1;j++)
    {
    max=0;
    //if(j==1&&i==3)
      //printf("%ld %ld %ld %ld %ld %ld\n",cat[1][2],cat[2][3],f[1][2],f[2][3],tong[1][2],tong[2][3]);
    for(long k=cat[j][j+i-2];k<=cat[j+1][j+i-1];k++)
       {
       if(min(f[j][k]+tong[j][k],f[k+1][j+i-1]+tong[k+1][j+i-1])>max)
          {
          max=min(f[j][k]+tong[j][k],f[k+1][j+i-1]+tong[k+1][j+i-1]);
          cat[j][j+i-1]=k;
          }
       }
    f[j][j+i-1]=max;
    //printf("%ld %ld %ld %ld\n",j,j+i-1,cat[j][j+i-1],f[j][j+i-1]);
    }
printf("%ld",f[1][n]);
//getch();
}

Code mẫu của ll931110

#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int f[2020][2020],pos[2020][2020];
int a[2020];
int n;

int main()
{
//  freopen("game.in","r",stdin);
//  freopen("game.ou","w",stdout);
    scanf("%d", &n);
    a[0] = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 2; i <= n; i++) a[i] += a[i - 1];
    memset(f,0,sizeof(f));
    for (int i = 1; i <= n; i++) pos[i][i] = i;
    for (int len = 2; len <= n; len++)
      for (int i = 1; i <= n - len + 1; i++)
      {
            int j = i + len - 1;            
            for (int t = pos[i][j - 1]; t <= pos[i + 1][j]; t++) if (t > 1)
            {
                int tmp = min(a[t - 1] - a[i - 1] + f[i][t - 1],a[j] - a[t - 1] + f[t][j]);
                if (f[i][j] < tmp)
                {
                    f[i][j] = tmp;  pos[i][j] = t;
                }
            }
    }
    printf("%d\n", f[1][n]);
}

Code mẫu của khuc_tuan

#include <cstdio>
using namespace std;

int n, a[2020], s[2020], F[2020][2020], T[2020][2020];

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) scanf("%d", a+i);  
    for(int i=1;i<=n;++i) s[i] = a[i-1] + s[i-1];
    for(int i=n-1;i>=0;--i) {
        T[i][i] = i;
        for(int j=i+1;j<n;++j) {
            for(int t=T[i][j-1];t<=T[i+1][j];++t) if(i<t) {
                int v = (F[i][t-1] + s[t]-s[i]) <? (F[t][j] + s[j+1] - s[t]);
                if(F[i][j] < v) {
                    F[i][j] = v;
                    T[i][j] = t;
                }
            }
        }
    }
    printf("%d\n", F[0][n-1]);
    return 0;
}