Cho xâu ký tự, loại bỏ một số ký tự để xâu còn lại là một dãy giảm dần

tengiday:

Ý tưởng của mình là giải theo quy hoạch động.

Mã:

F[i, j] = chuỗi lớn nhất khi xét từ vị trí s[1] tới s[i], và chữ số tận cùng là j, (1 <= i <= n; 0 <= j <= 9).

Công thức qhđ thì hơi phức tạp.

Mã:

F[i, j] = max( F[i - 1, j] và F[i, s[i]] = F[i - 1, j] * 10 + s[i] sao cho j > s[i] với j = 0..9.)

Khởi tạo giá trị của mảng F:

Mã:

F[1, s[0]] = s[0], còn lại 0 hết.

Kết quả sẽ là con số lớn nhất đc lưu ở dòng F[n,...]. Công thức trên là 2 trường hợp lấy s và không lấy s. Code đại khái của nó như thế này:

Mã:

 for i := 2 to n do
   begin
      for j := 0 to 9 do
         begin
            f[i, j] = f[i - 1, j];
            if (j > s[i] and f[i, s[i]] < f[i - 1, j] * 10 + s[i])
               update lại f[i, s[i]].
         end;
      Kiểm tra f[i, s[i]] với s[i]; và update cho f[i, s[i]].
   end;

Time complexity là O. Về bộ nhớ, có thể giảm mảng F còn 2 dòng vì chúng ta chỉ cần thông tin từ một hàng trước mà thôi. Mỗi lần chúng ta chỉ việc đổi 2 dòng qua lại, tức là mảng F có 20 phần tử là đủ. Ngoài ra, bạn cần lưu ý xử lý chuỗi nhé (có thể dùng int64 thay thế cho xử lý chuỗi).

Nhấn để mở rộng...

tài thế bác

tuongsonqt:

như vậy mảng f phải là mảng hai chiều hả bạn?

Nhấn để mở rộng...

luucan:

bạn tengiday ơi. bạn có thể giải thích rõ hơn 2 chỗ update lại f[i,s] và update cho f[i,s] cho mình được không? Mình không hiểu rõ lắm. Cảm ơn bạn rất nhiều!

Nhấn để mở rộng...

var s : ansistring;
    f : array[1..1000, 0..9] of int64;

function largest_number(s : ansistring) : int64;
var i, j : integer;
    k : int64;
begin
    // intialize array F
    for i := 1 to length(s) do
        for j := 0 to 9 do
            f[i, j] := 0;
    f[1, ord(s[1]) - 48] := ord(s[1]) - 48;
    
    // fill array F
    for i := 2 to length(s) do
        begin
            for j := 0 to 9 do
                begin
                    f[i, j] := f[i - 1, j];
                    if (j > ord(s[i]) - 48) then
                        begin
                            k := f[i - 1, j] * 10 + ord(s[i]) - 48;
                            if (f[i, ord(s[i]) - 48] < k) then
                                f[i, ord(s[i]) - 48] := k;
                        end;
                end;
            if (f[i, ord(s[i]) - 48] <= ord(s[i]) - 48) then
                f[i, ord(s[i]) - 48] := ord(s[i]) - 48;
        end;
        
    // tìm max
    k := f[length(s), 0];
    for i := 1 to 9 do
        if (k < f[length(s), i]) then
            k := f[length(s), i];
    exit(k);
end;