Cho xâu ký tự s chỉ bao gồm hai chữ cái là ‘A’ và ‘B’, độ dài không quá 1 triệu ký tự.
Mỗi bước được phép biến đổi một vị trí bất kỳ trong xâu (A thành B, B thành A) hoặc cũng có thể biến đổi một dãy liên tiếp các ký tự nào đó tính từ đầu xâu.Hãy tính xem cần ít nhất bao nhiêu bước để biến đổi xâu về dạng toàn chữ cái A.
VD:
input: AAABBBAAABBB
output: 4
các anh/chị có ý tưởng làm bài trên cho em tham khảo với ạ. em cảm ơn
bạn có hiểu đề bài vì sao ra 4 chưa?
có chứ a. nma để giải quyết tất cả TH thì cài đặt code hơi khó, với lai em sợ chưa xét đến tất cả các TH có thể xảy ra
còn để bài thì AAABBBAAABBB
-> BBBBBBAAABBB -> AAAAAAAAABBB -> BBBBBBBBBBBB -> AAAAAAAAAAAA
hỏi như vậy là để chắc rằng bạn hiểu ví dụ, vì đúng là bài này không đơn giản
vậy bạn có một giải pháp mà có thể mô phỏng bằng lời, mà người khác có thể dùng giải pháp đó để ra được đáp án đúng hay không?
hay với ví dụ trên thì bạn có thể nhẩm tính trường hợp này trường hợp kia các thứ và ra được như vậy (thay vì đổi từng cái), nhưng với một chuối dài hơn thì bạn có phương pháp nào để giải được hay không (ở đây chỉ nói cách giải bằng tay, chưa nói tới code)
Biết cách làm mà “sợ” không đủ trường hợp để rồi không làm thì chả khác nào bạn không biết.
Cứ làm đi bạn đến đâu, bị vấn đề gì thì hỏi tiếp.
Cứ làm từ từ, bắt đầu từ việc đơn giản.
bạn thử nghĩ về ý tưởng này
với một chuỗi chưa được hoàn thiện, ta luôn biểu diễn thành những kiểu sau
^A+B+ tức là bắt đầu bằng một số chữ A và sau đó là 1 số chữ B và hết. Gộp đoạn đầu này lại có 2 cách^B+A+ ngược lại với trường hợp (1)^A+B+A+ giống trường hợp 1 nhưng có cái đuôi phía sau (và hiển nhiên đuôi phía sau bắt đầu là A)
ta gộp 3 đoạn đầu lại, chi phí gộp tương tự (1)
^B+A+B+ gộp đoạn đầu này lại như sau
cách 1: biến từng chữ A thành B, sau đó biến cả đoạn thành A: chi phí = [số lượng A] + 1
cách 2: biến đoạn B đầu thành A (được ^A+B+), sau đó xét như cách 1 ta được: chi phí = 1 + min(2, countB)
với giải pháp như này (bạn cần hoàn thiện nó lại) thì có thể dùng đệ quy để giảm dần đồ phức tạp lại
hoặc bạn tử đưa về mảng số, với mỗi phần tử là số lượng chữ A hoặc B liên tục, A tính là 1, B tính là -1
AAABBBAAB có thể biến đổi thành 3 -3 2 -1
(3 chữ A liên tục tính là 3, 3 chữ B liên tục tính là -3, 2 chữ A liên tục tính là 2, 1 chữ B tính là -1)
rồi có thể dùng quy hoạch động để làm (hoặc nếu bạn dùng đệ quy như trên thì vẫn có thể sử dụng mảng số như này để tính toán cho tiện
#include <bits/stdc++.h>
using namespace std;
int ofa(string s, int start, int end, int len) {
int res;
int l_end = len - end;
int c1=0, // tu dau
c2=0, // le A
c3=0; // le B
for(int i=start; i<end; i++) {
if(s[i] == 'A') c2 += 1;
else c3 += 1;
if(i==end-1) break;
if(s[i+1] != s[i]) c1 += 1;
}
// c1
if(s[end] == 'B') {
if(l_end == 1) {
c1 += 1;
c3 += 1;
} else {
c1 += 2;
c3 += 2;
}
c2 += 1;
} else {
c1++;
c2++;
}
res = min(c1, c2);
res = min(res, c3);
return res;
}
void process() {
string s;
cin>>s;
int len = s.length();
int start = 0, end = len - 1;
while(s[start] == s[start+1]) start++;
while(s[end] == s[end-1]) end--;
cout<<ofa(s, start, end, len);
}
int main() {
process();
return 0;
}
vậy anh test giúp em với ạ, em làm và thử rồi nhưng nộp bài vẫn chưa đúng.
Mình vừa nghĩ ra, việc gộp 3 đoạn đầu tiên dạng XYX(với X một hoặc nhiều chữ A liên tục, Y là một hoặc nhiều chữ B liên tục, hoặc ngược lại) trở thành XXX sẽ tốn chi phí tối thiểu là 1 (nếu Y chỉ gồm 1 kí tự thì biến đổi kí tự đó luôn) và tối đa chỉ cần 2 bước (XYX bước đầu đổi đoạn đầu tiên thành Y sẽ được YYX, sau đó đổi nguyên đoạn đầu thành X được XXX)
như vậy chỉ cần lần lượt được 3 đoạn đầu tiên lại với nhau (2 nếu chỉ còn 2 đoạn) với chi phí tối ưu cho mỗi lần gộp
với mỗi bước gộp sẽ bớt đi 2 đoạn, và cứ thể gộp tiếp cho đến khi hết (lần gộp cuối nếu chỉ còn 2 đoạn thì hiển nhiên chi phí là 1)
Và sau khi gộp tất cả thành 1, nếu chuỗi gộp lúc này là BBBB… (toàn là B) thì cộng thêm 1 bước để đổi tất cả thành A
cách này chỉ cần 1 vòng lặp là xong, khỏi đệ quy
Update tí nữa
cách này bị sai với case này ABBBBABBB
như vậy cần xem xét trường hợp XYXY, việc biến đổi XYX thành XXX hoặc YYY đều tốn chi phí là 2, lúc này cần cách biến đổi thành YYY, vì sau đó dược YYYY, sẽ tối ưu hơn so với XXXY tốn thêm bước nữa để trở thành XXXX và có khi lại tốn thêm bước nữa để trở thành YYYY
Một lời khuyên nữa, khi bạn còn chưa vạch ra được giải pháp rõ ràng thì chẳng thể nào code được pass đâu (trừ khi testcase không phủ hết tất cả các case)
có lẽ đầu tiên biến các chữ B đứng riêng lẻ thành A
rồi sau đó biến các chữ A riêng lẻ thành B
rồi sau đó tiến hành biến đổi dãy liên tiếp từ đầu xâu
ko biết vậy có đúng ko 
int countChanges(std::string s) {
if (s.empty()) return 0;
if (s.size() == 1) return s[0] == 'B';
int res = 0;
int n = s.size();
// Chuyển ký tự đứng riêng lẻ
auto countSingleChange = [&](char from, char to) {
if (s[0] == from && s[1] == to) s[0] = to, ++res;
if (s[n-1] == from && s[n-2] == to) s[n-1] = to, ++res;
for (int i = 1; i < n-1; ++i)
if (s[i] == from && s[i-1] == to && s[i+1] == to) s[i] = to, ++res;
};
// Chuyển B riêng lẻ thành A
countSingleChange('B', 'A');
// Chuyển A riêng lẻ thành B
countSingleChange('A', 'B');
// Chuyển nhiều ký tự
std::adjacent_find(begin(s), end(s), [&](char a, char b) {
res += a != b;
return false;
});
res += s[n-1] == 'B';
return res;
}
thử xem hên xui 
Bài này chắc là dùng quy hoạch động sẽ ra thôi.
Gọi s là input. dp[i] là số phép biến đổi nhỏ nhất cho đoạn s[0:i]. dpx[i] là số phép biến đổi nhỏ
nhất cho nghịch đảo của đoạn s[0:i].
Vậy ta sẽ có:
s[i] là A: chỉ cần biến đổi s[0:i-1], tức là bằng dp[i-1]
s[i] là B: có hai cách biến đổi:
s[i] thành A rồi biến đổi đoạn s[0:i-1], tức là 1 + dp[i-1]
s[0:i] rồi biến đổi đoạn s[0:i-1] đã bị nghịch đảo, tức là 1 + dpx[i-1]
Suy ra công thức truy hồi:
dp[0] = 0 if s[0]=='A' else 1
dpx[0] = 0 if s[0]=='B' else 1
dp[i+1] = dp[i] if s[i]=='A' else min(dp[i]+1, dpx[i]+1)
dpx[i+1] = dpx[i] if s[i]=='B' else min(dp[i]+1, dpx[i]+1)
def f(s):
dp = [0]*len(s)
dpx = [0]*len(s)
dp[0] = 0 if s[0]=='A' else 1
dpx[0] = 0 if s[0]=='B' else 1
for i in range(1, len(s)):
x = min(dp[i-1]+1, dpx[i-1]+1)
dp[i] = dp[i-1] if s[i]=='A' else x
dpx[i] = dpx[i-1] if s[i]=='B' else x
return dp[-1]
s='AAABBBAAABBB'
print(f(s))
anh cho em hỏi cái nghịch đảo của đoạn là sao vậy ạ
anh giải thích giúp em trường hợp này với ạ
Lấy ví dụ s=AAABBB, thì khi biến đổi đến chữ B cuối cùng, ta có 2 cách:
B thành A rồi biến đổi AAABB thành AAAAA
BBBAAA rồi biến đổi BBBAA thành AAAAA (thì trong này, cái chuỗi BBBAA gọi là chuỗi nghịch đảo, hoặc chuỗi đã bị biến đổi)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?