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;
      max=100000000;
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
          read(t);
          a[i]:=a[i-1]+t;
     end;
     close(input);
end;

procedure pr;
var i,j,l,t,u:longint;
begin
     for i:=1 to n do
         for j:=i+1 to n do
         begin
              f[i,j]:=max; f[j,i]:=f[i,j];
         end;
     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
                   u:=a[j]-a[i-1]+f[i,t-1]+f[t,j];
                   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 happyboy99x

#include<cstdio>

const int N = 2e3+1, INF = 1e9;
int a[N], s[N], f[N][N], p[N][N], n;

void enter() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
    }
}

void solve() {
    for(int i = 1; i <= n; ++i)
        f[i][i] = 0, p[i][i] = i;
    for(int l = 2; l <= n; ++l)
        for(int i = 1, j = i + l - 1; j <= n; ++i, ++j) {
            f[i][j] = INF;
            for(int t = p[i+1][j]; t >= p[i][j-1]; --t)
                if(s[j] - s[i-1] + f[i][t-1] + f[t][j] < f[i][j]) {
                    f[i][j] = s[j] - s[i-1] + f[i][t-1] + f[t][j];
                    p[i][j] = t;
                }
        }
    printf("%d\n", f[1][n]);
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 2002;
const int oo = 2000000009;
using namespace std;

int a[N], sum[N];
int F[N][N], P[N][N];
int n;

int main()
{
    scanf("%d", &n);
    int i, j, k, new_F;
    for(i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    for(i=1; i<=n; i++) P[i][i] = i - 1;
    for(int len = 1; len <= n; len++)
    for(i = 1; i <= n - len; i++) {
        j = i + len; F[i][j] = oo;
        for(k = P[i][j - 1]; k <= P[i + 1][j]; k++) {
        //for(k=i; k<j; k++) {
            new_F = F[i][k] + F[k + 1][j];
            if (F[i][j] > new_F) {
                F[i][j] = new_F;
                P[i][j] = k;
            }
        }
        F[i][j] += sum[j] - sum[i - 1];
    }
    cout << F[1][n];
    return 0;
}

Code mẫu của RR

// http://codeforces.com/blog/entry/8219
// Original Recurrence:
//   dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j]   for k = i+1..j-1
// Necessary & Sufficient Conditions:
//   A[i][j-1] <= A[i][j] <= A[i+1][j]
//   with A[i][j] = smallest k that gives optimal answer
// Also applicable if the following conditions are met:
//   1. C[a][c] + C[b][d] <= C[a][d] + C[b][c] (quadrangle inequality)
//   2. C[b][c] <= C[a][d]                     (monotonicity)
//   for all a <= b <= c <= d
// To use:
//   Calculate dp[i][i] and A[i][i]
//
//   FOR(len = 1..n-1)
//     FOR(i = 1..n-len) {
//       j = i + len
//       FOR(k = A[i][j-1]..A[i+1][j])
//         update(dp[i][j])
//     }

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

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

#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 EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#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; }

#define sqr(x) ((x) * (x))
using namespace std;


const int MN = 2011;
int a[MN], dp[MN][MN], C[MN][MN], A[MN][MN];
int n;

int main() {
    while (cin >> n) {
        FOR(i,1,n) {
            cin >> a[i];
            a[i] += a[i-1];
        }
        FOR(i,1,n) FOR(j,i,n) C[i][j] = a[j] - a[i-1];

        FOR(i,1,n) dp[i][i] = 0, A[i][i] = i;

        FOR(len,1,n-1)
            FOR(i,1,n-len) {
                int j = i + len;
                dp[i][j] = 2000111000;
                FOR(k,A[i][j-1],A[i+1][j]) {
                    int cur = dp[i][k-1] + dp[k][j] + C[i][j];
                    if (cur < dp[i][j]) {
                        dp[i][j] = cur;
                        A[i][j] = k;
                    }
                }
            }
        cout << dp[1][n] << endl;
    }
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long cat[2001][2001],n,a[2001],tong[2001][2001],f[2001][2001],min;
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];
    }
for(long i=1;i<=n;i++)
  {
  f[i][i]=0;
  cat[i][i]=i;
  if(i!=n)  
    {
    f[i][i+1]=tong[i][i+1];
    cat[i][i+1]=i;
    }
  }
for(long i=3;i<=n;i++)
  for(long j=1;j<=n-i+1;j++)
    {
    min=2000000000;       
    //if(j==1&&i==3)
      //printf("%ld %ld\n",/*f[j][2]+f[3][j+i-1]*/f[j][1],f[2][3]);       
    for(long k=cat[j][j+i-2];k<=cat[j+1][j+i-1];k++)
      {
      //printf("%lld\n",f[j][k]+f[k+1][j+i-1]);       
      if(min>f[j][k]+f[k+1][j+i-1])
        {
        min= f[j][k]+f[k+1][j+i-1];
        cat[j][j+i-1]=k;     
        }
      }
    f[j][j+i-1]=min+tong[j][j+i-1];  
    //printf("%ld %ld %ld %lld\n",i,j,cat[j][j+i-1],f[j][j+i-1]);
    }
printf("%lld",f[1][n]);
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program OPTCUT3;
Const
  input  = '';
  output = '';
  maxn = 2000;
  maxv = 500000000;
Var
  a: array[1..maxn] of integer;
  k,f,w: array[1..maxn,1..maxn] of integer;
  n: integer;

Procedure init;
Var
  fi: text;
  i: integer;
Begin
  Assign(fi, input);
    Reset(fi);

  Readln(fi, n);
  For i:= 1 to n do read(fi, a[i]);

  Close(fi);
End;

Procedure gens;
Var
  i,j: integer;
Begin
  For i:= 1 to n do
    For j:= 1 to n do
      F[i,j]:= maxv;

  For i:= 1 to n do w[i,i]:= a[i];
  For i:= 1 to n - 1 do
    For j:= i + 1 to n do w[i,j]:= w[i,j - 1] + a[j];
End;

Procedure solve;
Var
  l,i,j,t,v: integer;
Begin
  For i:= 1 to n do
    Begin
      F[i,i]:= 0;
      k[i,i]:= i;
    End;

  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 if t <> 1 then
          Begin
            v:= w[i,j] + f[i,t - 1] + f[t,j];
            If f[i,j] > v then
              Begin
                f[i,j]:= v;
                k[i,j]:= t;
              End;
          End;
      End;
End;

Procedure printresult;
Var
  fo: text;
Begin
  Assign(fo, output);
    Rewrite(fo);
    Writeln(fo, F[1,n]);
  Close(fo);
End;

Begin
  init;
  gens;
  solve;
  printresult;
End.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   2020
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
const int INF=(int)1e9+7;
int f[MAX][MAX],t[MAX][MAX];
int a[MAX],s[MAX];
int n;
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
}
int sum(int l,int r) {
    return (s[r]-s[l-1]);
}
void optimize(void) {   
    FOR(i,1,n-1) {
        f[i][i+1]=sum(i,i+1);
        t[i][i+1]=i;
    }
    FOR(i,3,n) FOR(j,1,n-i+1) {
        int l=j;
        int r=j+i-1;
        f[l][r]=INF;
        FOR(k,t[l][r-1],t[l+1][r])
            if (f[l][r]>f[l][k]+f[k+1][r]) {
                f[l][r]=f[l][k]+f[k+1][r];
                t[l][r]=k;
            }
        f[l][r]+=sum(l,r);
    }
    printf("%d",f[1][n]);
}
int main(void) {
    init();
    optimize();
    return 0;
}

Code mẫu của khuc_tuan

//{$Q+,R+,S+}
// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math;

var
    i, j, k, n : integer;
    a : array[0..2000] of integer;
    t, F : array[0..2000,0..2000] of integer;

begin
    read(n);
    for i:=1 to n do
    begin
        read(a[i]);
        inc(a[i], a[i-1]);
    end;
    for i:=n downto 1 do
    begin
        t[i,i] := i;
        for j:=i+1 to n do
        begin
            F[i,j] := 1000000000;
            for k:= t[i,j-1] to t[i+1,j] do if k < j then 
            begin
                if F[i,j] > F[i,k] + F[k+1,j] then
                begin
                    F[i,j] := F[i,k] + F[k+1,j];
                    t[i,j] := k;
                end;
            end;
            inc( F[i,j], a[j] - a[i-1]); 
        end;
    end;
    writeln( F[1,n]);
end.