Tạo bài viết
Đăng ký
02/10/2018, 14:52

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 1 , x 2 , .., x m và Y = y 1 , y 2 , …, y n . Cần xây dựng xâu T = t 1 , t 2 , t 3 , ..,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 ...

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

1. Đề bài STMERGE spoj

Cho 2 xâu ký tự X = x1, x2, .., xm và Y = y1, y2, …, yn. Cần xây dựng xâu T = t1, t2, t3, ..,tn+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(tk, tk+1 )) với k = 1, 2, ..,  n+m-1; trong đó, các chi phí c(tk, tk+1) được tính như sau:

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

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(xi, y1), c(xi, y2), …, c(xi, yn), 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:

1

2 3

3 2 30

15 5 4

output:

6

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])<<" "; } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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])<<" ";
    }
}

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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.

Trần Trung Dũng

15 chủ đề

2610 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024