Đề bài:

• http://vn.spoj.com/problems/NKPANO/

Thuật toán:

• Sắp xếp các công nhân tăng dần theo S
• Gọi F[i] là tổng tiền công lớn nhất nếu sơn đến vạch i.
  Với mỗi công nhân thứ k: F[i]=max(F[i],F[j-1]+(i-j+1)*P[k]), trong đó: S[k]<=i<=S[k]+L[k]-1, i-L[k]+1<=j<=S[k]

Code:

• xem code trên ideone

#include 
#define maxn 16010
using namespace std;
int n,k,l;
int f[maxn+1],maxf[maxn+1],maxr[maxn+1];
struct  te{
    int l,p,s;
};
te a[102];
template  inline void read(T &x){
	x = 0; char c;
	while (!isdigit(c = getchar())) {}
	do x = x * 10 + c - '0'; while (isdigit(c = getchar()));
}
template  inline void write(T x){
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
void    docdl(){
    read(n); read(k);
    for(int i=1;i<=k;i++){
        read(a[i].l);
        read(a[i].p);
        read(a[i].s);
    }
}
bool    cmp(te a,te b){
    return (a.s<=b.s);
}
void    xuli(){
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        maxr[a[i].s+1]=-1000000000;
        for(int j=a[i].s;j>=max(a[i].s-a[i].l+1,1);j--) maxr[j]=max(maxr[j+1],maxf[j-1]-(int)j*a[i].p);
        for(int j=a[i].s;j<=min(a[i].s+a[i].l-1,n);j++){
            f[j]=max(f[j],maxr[max(j-a[i].l+1,1)]+(int)(j+1)*a[i].p);
            maxf[j]=max(f[j],maxf[j-1]);
        }
        for(int j=1;j<=n;j++) maxf[j]=max(maxf[j],maxf[j-1]);
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    write(res);
}
int     main(){
    docdl();
    xuli();
}

Đề bài: http://vn.spoj.com/problems/PETROLM/

Thuật toán:

• Đây là một bài QHĐ cơ bản suy nghĩ một chút sẽ ra
• Các bạn hãy đọc code của mình sẽ hiểu ngay

Code:

uses math;
const
  fi='';//petrolm.inp';
  fo='';//petrolm.out';
  maxn=4000;
  oo=trunc(1e18);
type
  arr1 = array[1..maxn] of longint;
var
  tram,xe,csxe,cstram,kq : array[1..maxn] of longint;
  f : array[0..maxn,0..maxn] of int64;
  i,j,n,m : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(xe[i]);
    read(m);
    for i:=1 to m do read(tram[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a,b : arr1);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
      while x>a[i] do inc(i);
      while xj;
    if il then qs(l,j,a,b);
  end;
procedure process;
  begin
    for i:=1 to n do csxe[i] := i;
    for i:=1 to m do cstram[i] := i;
    qs(1,n,xe,csxe);
    qs(1,m,tram,cstram);
    for i:=0 to n do
      for j:=0 to n do
        f[i,j] := oo;
    f[0,0] := 0;
    for i:=1 to n do f[i,i] := f[i-1,i-1] + abs(xe[i]-tram[i]);
    for j:=1 to m do
      for i:=j+1 to n do
        begin
          f[i,j] := min(f[i-1,j-1] + abs(xe[i]-tram[j]), f[i-1,j] + abs(xe[i]-tram[j]) );
          f[i,j] := f[i,j];
        end;
  end;
procedure print;
  begin
    assigN(output,fo);rewrite(output);
    writeln(f[n,m]);
    i:=n; j:= m;
    while (i>0) and (j>0) do
      begin
        if f[i,j]=f[i-1,j-1] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);dec(j);
            continue;
          end;
        if f[i,j]=f[i-1,j] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);
            continue;
          end;
      end;
    for i:=1 to n do write(kq[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

Đề bài: http://vn.spoj.com/problems/COUNTPL/

Thuật toán:

• Tính trước mảng pan[i][j] = true nếu xâu s[i..j] là palindrome và ngược lại
• Gọi f[i][j]=true nếu xâu s[1..i] có thể chia làm j xâu palindrome và ngược lại
• Code đoạn tính f[i][j] cho các bạn dễ hiểu:

        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        oo=1000;
var     pan     :array[1..maxn,1..maxn] of boolean;
        i,j,n   :longint;
        s       :string;
        f       :array[0..maxn,0..maxn] of boolean;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(s);
        close(input);
end;
function check(i,j      :longint):boolean;
var     tg      :string;
begin
        tg := copy(s,i,j-i+1);
        for i :=1 to length(tg) div 2 do
                if tg[i]<>tg[length(tg)-i+1] then exit(false);
        exit(true);
end;
procedure process;
var     i,j,k   :longint;
begin
        n := length(s);
        for i:=1 to n do
                for j:=i to n do
                        if check(i,j) then pan[i,j] := true;
        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.