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>
using namespace std;

int value[51],a[51],n,g[51][51],f[51][101],ans;

int main()
{
    int x,y,m;
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    cin >> m;
    while (m--) cin >> x >> y, value[x]=max(value[x],y);
    // precalc for each bar
    for (int i=1;i<=50;i++) g[i][0]=-1000000;
    for (int i=1;i<=50;i++)
        for (int j=1;j<=i;j++)
            for (int ii=0;ii<i;ii++)
                g[i][j]=max(g[i][j],g[ii][j-1]+value[i-ii]);
    // dp
    for (int i=1;i<=n;i++)
        for (int j=1;j<=a[i];j++)
            for (int k=j-1;k<=100;k++)
                f[i][k]=max(f[i][k],f[i-1][k-j+1]+g[a[i]][j]);
    for (int k=0;k<=100;k++) ans=max(ans,f[n][k]-k*(k+1)/2);
    cout << ans << endl;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 53;
const int lim = 73;
using namespace std;

int F[N][N][lim];
int res, n, m;
int a[N], val[N];

void maximize(int &a, int b)
    {a = a > b ? a : b; res = res > a ? res : a;}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    int d, v;
    for(int i = 1; i <= m; i++) {
        cin >> d >> v;
        val[d] = v;
    }
    memset(F, 255, sizeof F);
    F[1][a[1]][0] = 0;
    for(int i = 1; i <= n; i++)
    for(int j = a[i]; j; j--)
    for(int k = 0; k < lim - 1; k++) 
    if (F[i][j][k] != -1) {
        for(int t = 1; t < j; t++)
            maximize(F[i][j - t][k + 1], F[i][j][k] + val[t] - k - 1);
        maximize(F[i + 1][a[i + 1]][k], F[i][j][k] + val[j]);
    }
    cout << res;
    return 0;
}

Code mẫu của RR

{$R+,Q+}
PROGRAM CATGO;
CONST
  FINP='';
  FOUT='';
  max=52;
VAR
  t,n,m:integer;
  gt:array[0..max] of longint;
  c:array[1..max] of longint;
  d:array[1..max,0..max*max] of longint;
  kq:array[0..max,0..max*max] of longint;
procedure readInput;
var
  f:text;
  u,i:integer;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do
    read(f,c[i]);
  read(f,m);
  for i:=1 to m do
    begin
      read(f,u,gt[u]);
      d[u,0]:=gt[u];
    end;
  close(f);
end;
function max2(a,b:longint):longint;
begin
  if a>b then max2:=a else max2:=b;
end;
procedure writeOutput;
var
  f:text;
  answer,i:longint;
begin
  assign(f,FOUT); rewrite(f);
  answer:=0;
  for i:=0 to t do
    answer:=max2(answer,kq[n,i]);
  writeln(f,answer);
  close(f);
end;
procedure QHD1;
var
  i,j,k:integer;
begin
  for i:=1 to max do
    for j:=1 to i-1 do
      for k:=1 to i-1 do
        d[i,j]:=max2(d[i,j],d[k,j-1]+gt[i-k]);
end;
function min2(a,b:longint):longint;
begin
  if a<b then min2:=a else min2:=b;
end;
procedure QHD2;
var
  i,j,k,u,g,l,gg:integer;
begin
  t:=0;
  for i:=1 to n do
    begin
      u:=c[i]; l:=t; t:=t+u-1;
      gg:=min2(t,max);
      for j:=0 to gg do
      begin
        g:=min2(l,j);
        g:=min2(max,g);
        for k:=0 to g do
          kq[i,j]:=max2(kq[i,j],kq[i-1,k]+d[u,j-k]+k*(k+1) div 2-j*(j+1) div 2);
      end;
    end;
end;
BEGIN
  readInput;
  QHD1;
  QHD2;
  writeOutput;
END.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
int n,m,kt[51],dai[51],gia[51];
int d[51][51],flag[51],f[51][53];


int main()
{
    //freopen("CATGO_10.in","r",stdin);
    for(int i = 0;i<=50;i++)
    {
        flag[i]=0;
        for(int j = 0;j<=50;j++)
        {
            d[i][j]=0;
            f[i][j]=0;
        }
    }

    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
        scanf("%d",&kt[i]);
    scanf("%d",&m);   
    for(int i = 1;i<=m;i++)
    {
        scanf("%d %d",&dai[i],&gia[i]);
        flag[dai[i]]=i;
    }        
    for(int i = 1;i<=50;i++)
        for(int j = 0;j<=50;j++)
        {
            if(j==0)
            {
                   if( flag[i]!=0)
                d[i][j]=gia[flag[i]];
            }
            else 
            {
                int max=0;
                for(int k = 1;k<=i-1;k++)
                    if(d[k][j-1]+d[i-k][0]>max)
                        max = d[k][j-1]+d[i-k][0];
                d[i][j]=max;
            }
            //if(i==10) printf("%d %d %d\n",j,d[i][j],flag[10]);
        }
    for(int i = 1;i<=n;i++)
        for(int j = 0;j<=52;j++)
        {
            if(i==1)
                f[i][j]=d[kt[i]][j];
            else 
            {
                int max = 0;
                for(int k = 0;k<=j;k++)
                    if(f[i-1][k]+d[kt[i]][j-k]>max)
                        max = f[i-1][k]+d[kt[i]][j-k];
                f[i][j] = max;
            }
        }
    int Max = 0;
    for(int i=0;i<=52;i++)
        if(f[n][i]-i*(i+1)/2>Max)
        {
            Max = f[n][i]-i*(i+1)/2;
           // printf("%d %d %d\n",i,f[n][i],Max);
        }
    printf("%d",Max);
    //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,m;
int g[52][52],f[52][502];
int a[52],len[52],val[52];

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

    memset(g,0,sizeof(g));
    for (int i = 0; i < m; i++) g[len[i]][0] = max(g[len[i]][0],val[i]);
    for (int j = 1; j < 50; j++)
      for (int i = 1; i <= 50; i++)
        for (int t = 0; t < m; t++) if (i >= len[t]) g[i][j] = max(g[i][j],g[i - len[t]][j - 1] + val[t]);

    memset(f,0,sizeof(f));
    for (int i = 1; i <= n; i++)
      for (int j = 0; j <= 500; j++)
        for (int t = 0; t < a[i] && t <= j; t++) f[i][j] = max(f[i][j],f[i - 1][j - t] + g[a[i]][t]);

    int best = 0;
    for (int i = 0; i <= 500; i++) best = max(best,f[n][i] - i * (i + 1) / 2);
    printf("%d\n", best);
};

Code mẫu của khuc_tuan

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[55];
        for (int i = 0; i < m; ++i) {
            int x = sc.nextInt();
            v[x] = sc.nextInt();
        }
        int[][] f = new int[55][55];
        for (int i = 0; i < f.length; ++i)
            for (int j = 0; j < f[i].length; ++j)
                if (j == 0)
                    f[i][j] = v[i];
                else
                    for (int len = 1; len < i; ++len)
                        f[i][j] = Math.max(f[i][j], f[i - len][j - 1] + v[len]);
        int[][] g = new int[n][1000];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < g[i].length; ++j)
                for (int t = 0; t < 55 && t <= j; ++t)
                    g[i][j] = Math.max(g[i][j], (i == 0 ? 0 : g[i - 1][j - t])
                            + f[a[i]][t]);
        int total = 0;
        int res = 0;
        for (int x = 0; x < 1000; ++x) {
            total += x;
            res = Math.max(res, g[n - 1][x] - total);
        }
        System.out.println(res);
    }
}