STMERGE spoj - VOI 2013 - Trộn xâu

Nguồn đề bài: http://vn.spoj.com/problems/STMERGE/

1. Đề bài STMERGE spoj

Cho 2 xâu ký tự X = x₁, x₂, .., x_m và Y = y₁, y₂, …, y_n. Cần xây dựng xâu T = t₁, t₂, t₃, ..,t_n+m_.gồm tất cả các ký tự trong xâu X và tất cả các ký tự trong xâu Y, sao cho các ký tự trong X xuất hiện trong T theo thứ tự xuất hiện trong X và các ký tự trong Y xuất hiện trong T theo đúng thứ tự xuất hiện trong Y, đồng thời với tổng chi phí trộn là nhỏ nhất. Tổng chi phí trộn hai xâu X và Y để thu được xâu T được tính bởi công thức c(T) = sum(c(t_k, t_k+1 )) với k = 1, 2, .., n+m-1; trong đó, các chi phí c(t_k, t_k+1) được tính như sau:

Nếu hai ký tự liên tiếp t_k, t_k+1 được lấy từ cùng một xâu X hoặc Y thì c(t_k, t_k+1) = 0
Nếu hai ký tự liên tiếp t_k, t_k+1 là x_i y_j thì chi phí phải trả là c(x_i, y_j). Nếu hai ký tự liên tiếp t_k, t_k+1 là y_j, x_i thì chi phí phải trả là c(y_j, x_i) = c(x_i, y_j)

Input

Dòng đầu tiên chứa Q là số lượng bộ dữ liệu. tiếp đến là Q nhóm dòng, mỗi nhóm cho thong tin về 1 bộ dữ liệu theo khuôn dạng sau:

Dòng thứ nhất chứa 2 số nguyên duong m, n (m, n <= 1000);
Dòng thứ i trong m dòng tiếp theo chứa n số nguyên dương, mỗi số không vượt quá 10^9: c(x_i, y₁), c(x_i, y₂), …, c(x_i, y_n), i = 1, 2,…, m.

Ràng buộc : Có 60% số test ứng với 60% số điểm của bài đó có m, n <= 10

Output

Gồm Q dòng, mỗi dòng chứa một số nguyên là tổng chi phí theo cách xây dựng xâu T tìm được tương ứng với bộ dữ liệu vào.

Example

Input:

2 3

3 2 30

15 5 4

output:

2. Hướng dẫn STMERGE spoj

Thuật toán quy hoạch động:

Gọi F[i][j][k] là tổng nhỏ nhất tạo thành từ xâu X[1..i] và Y[1..j], trong đó với k = 0 tương ứng trường hợp kí tự cuối là Y[j] và k = 1 tương ứng kí tự cuối là X[i]

* Trường hợp kí tự cuối là Y[j], tức F[i][j][0], thì kí tự trước đó có hai trường hợp:

– Y[j-1] Y[j] :

F[i][j][0] = F[i][j-1][0]

– X[i] Y[j] :

f[i][j][0] = f[i][j-1][1] + c[i][j]

* Trường hợp kí tự cuối là X[i], tức F[i][j][1], thì kí tự trước đó có hai trường hợp

– X[i-1] X[i] :

f[i][j][1] = f[i-1][j][1]

– Y[j] X[i] :

f[i][j][1] = f[i-1][j][0] + c[i][j]

3. Code mẫu STMERGE spoj Pascal và c++

a. code c++

#include <bits/stdc++.h>

using namespace std;
    int q,m,n,c[1001][1001];
    long long f[1001][1001][2];
int main()
{
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>m>>n;
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
        {
            cin>>c[i][j];
            f[i][j][0]=f[i][j][1]=0;
        }
        f[1][1][0] = f[1][1][1] = c[1][1];
        for(int j=2; j<=n; j++)
        {
            f[1][j][0]=min(f[1][j-1][0],
                           f[1][j-1][1]+c[1][j]);
            f[1][j][1]=c[1][j];
        }
        for(int i=2; i<=m; i++)
        {
            f[i][1][0]=c[i][1];
            f[i][1][1]=min(f[i-1][1][1],
                           f[i-1][1][0]+c[i][1]);
        }
        for(int i=2; i<=m; i++)
            for(int j=2; j<=n; j++)
        {
            f[i][j][0]=min(f[i][j-1][0],
                           f[i][j-1][1]+c[i][j]);
            f[i][j][1]=min(f[i-1][j][1],
                           f[i-1][j][0]+c[i][j]);
        }
        cout<<min(f[m][n][0],f[m][n][1])<<"\n";
    }
}

b. Code pascal

const   fi='STMERGE.INP';
        fo='STMERGE.OUT';
        nmax=1000;
type    data=longint;
var     f:text;
        n,m,test:data;
        C:array[0..nmax+1,0..nmax+1] of data;
        A:array[0..nmax+1,0..nmax+1,0..1] of data;
function min(a,b:data):data;
begin
        if a<b then exit(a); exit(b);
end;
procedure qhd;
var     i,j,k:data;
begin
        A[1,1,1]:=C[1,1];
        A[1,1,0]:=C[1,1];
        for i:=2 to n do
                begin
                        a[1,i,1]:=C[1,i];
                        a[1,i,0]:=min(a[1,i-1,0],A[1,i-1,1]+C[1,i]);
                end;
        for i:=2 to m do
                begin
                        a[i,1,0]:=C[i,1];
                        a[i,1,1]:=min(a[i-1,1,1],A[i-1,1,0]+C[i,1]);
                end;
       for i:=2 to m do
                for j:=2 to n do
                        begin
                                a[i,j,0]:=min(a[i,j-1,0],a[i,j-1,1]+c[i,j]);
                                a[i,j,1]:=min(a[i-1,j,1],a[i-1,j,0]+c[i,j]);
                        end;
        writeln(min(A[m,n,0],a[m,n,1]));
end;

procedure docfile;
var     i,j,t:data;
begin
        assign(f,fi); reset(f);
        readln(f,test);
        for t:=1 to test do
                begin
                        read(f,m,n);
                        for i:=1 to m do
                                for j:=1 to n do
                                        read(f,c[i,j]);
                        qhd;
                end;
        close(f);
end;
begin
        docfile;
end.

STMERGE spoj – VOI 2013 – Trộn xâu