kết quả từ 1 tới 8 trên 8

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

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    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

    Cho trước một xâu ký tự gồm toàn các chữ số. hãy loại bỏ một số ký tự khỏi xâu sao cho các ký tự cuối cùng còn lại là một dãy giảm dần và theo đúng thứ tự đó tạo nên một số lớn nhất. ví dụ nếu cho xâu '64562372361247120686005007710137667690' thì số lớn nhất còn lại là 764210.
    hãy lập trình chương trình để giả bài toán trên.
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: các bạn xem bài xâu này cho mình với

    Ý 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[i] và không lấy s[i]. 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(n). 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).
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. 4 thành viên đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 280098
    Giới tính: Nam
    Bài gửi
    2.051

    Reply: các bạn xem bài xâu này cho mình với

    Trích Nguyên văn bởi tengiday Xem bài viết
    Ý 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[i] và không lấy s[i]. 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(n). 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).
    tài thế bác
    Nhận tư vấn các vấn đề về Tình Yêu

  5. Đã cảm ơn Joinal457:


  6. #4
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: các bạn xem bài xâu này cho mình với

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

  7. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: các bạn xem bài xâu này cho mình với

    Trích Nguyên văn bởi tuongsonqt Xem bài viết
    như vậy mảng f phải là mảng hai chiều hả bạn?
    Đúng rồi đó bạn. Nếu tối ưu thì mảng F gồm 2 dòng và 10 cột, kiểu int64.

  8. Đã cảm ơn tengiday:


  9. #6
    Ðến Từ
    Thanh Hóa
    Thành Viên Thứ: 378374
    Bài gửi
    3

    Reply: các bạn xem bài xâu này cho mình với

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

  10. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: các bạn xem bài xâu này cho mình với

    Trích Nguyên văn bởi luucan Xem bài viết
    bạn tengiday ơi. bạn có thể giải thích rõ hơn 2 chỗ update lại f[i,s[i]] và update cho f[i,s[i]] cho mình được không? Mình không hiểu rõ lắm. Cảm ơn bạn rất nhiều!
    Đoạn code của function đó đây nhé bạn. Như vậy dễ xem hơn.
    Mã:
    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;


    Bài này có thể tối ưu bộ nhớ bằng cách dùng mảng chỉ gồm 2 dòng thôi.

  11. Đã cảm ơn tengiday:

    luucan 

  12. #8
    Ðến Từ
    Thanh Hóa
    Thành Viên Thứ: 378374
    Bài gửi
    3

    Reply: các bạn xem bài xâu này cho mình với

    Cảm ơn bạn rất nhiều nhé!

  13. Đã cảm ơn luucan: