VOI 13 Bài 4 - Trộn xâu - VNOJ: VNOI Online Judge

VOI 13 Bài 4 - Trộn xâu

Điểm: 0,27 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

VOI 2013 - Ngày 2

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~, 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\left(T\right) = \sum_{k = 1}^{n + m - 1}c\left(t_{k}, t_{k+1}\right)~; trong đó, các chi phí ~c\left(t_{k}, t_{k+1}\right)~ đượ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\left(t_{k}, t_{k+1}\right) = 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\left(x_{i}, y_{j}\right)~. 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\left(y_{j}, x_{i}\right) = c\left(x_{i}, y_{j}\right)~

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 \le 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\left(x_{i}, y_{1}\right)~, ~c\left(x_{i}, y_{2}\right)~, ..., ~c\left(x_{i}, y_{n}\right)~, ~i = 1~, ~2~, ..., ~m~.

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.

Giới hạn

Có 60% số test ứng với 60% số điểm của bài đó có ~m~, ~n \leq 10~

Sample Input

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

-4

Huy_inIT đã bình luận lúc 8, Tháng 8, 2024, 14:19

include <bits/stdc++.h>

define fastbuild ios::syncwithstdio(false); cin.tie(0);

typedef long long ll; const int inf = 1e8; using namespace std;

int dp[1002][1002][2];

signed main() { fastbuild; int t; cin >> t; while(t--) { int n, m; cin >> n >> m; int cost[n][m]; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> cost[i][j]; } }

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            dp[i][j][0] = dp[i][j][1] = inf;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        dp[i][0][0] = 0;
    }

    for(int j = 1; j <= m; j++)
    {
        dp[0][j][1] = 0;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1] + cost[i-1][j-1]);
            dp[i][j][1] = min(dp[i][j-1][0] + cost[i-1][j-1], dp[i][j-1][1]);
        }
    }

    cout << min(dp[n][m][0], dp[n][m][1]) << endl;
}
return 0;

}

-6

Huy_inIT đã bình luận lúc 8, Tháng 8, 2024, 13:06

bài này dễ v để làm

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-16

trongtenlinhcbhk64 đã bình luận lúc 10, Tháng 12, 2023, 19:36

~x_1 x_2~

~y_1 y_2 y_3~

~y_1 y_2 x_1 x_2 y_3~

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.