傳送門
題目：題目目標串有類似遞回的要求，可以看出在左邊界或者有邊界存在連續的字符且是上個連續字符長度的一半，字符則是上個字符的下一個字符，
思路：容易想到二分，深度log(n)，則復雜度O（n*log(n)），
我們可以直接分兩種情況：
①左半邊連續字符相同
②右半邊連續字符相同
我們把這個作為遞回條件即可，統計花費的時候我們只需要判斷當前連續部分字符是不是我們的目標字符來計算花費即可，
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 #include <vector> 6 #include <cmath> 7 8 using namespace std; 9 10 #define ll long long 11 #define pb push_back 12 #define fi first 13 #define se second 14 15 const int N = 2e5 + 10; 16 char s[N]; 17 int len; 18 19 int dfs(int l, int r, char c) 20 { 21 22 if(l == r){ 23 if(s[l] == c) return 0; 24 else return 1; 25 } 26 int mid = (l + r) >> 1; 27 int min_cost = 2e9; 28 int a1 = 0, b1 = 0; 29 for(int i = l; i <= mid; ++i){ 30 if(s[i] != c) a1++; 31 } 32 33 min_cost = min(min_cost, a1 + dfs(mid + 1, r, c + 1)); 34 a1 = b1 = 0; 35 for(int i = mid + 1; i <= r; ++i){ 36 if(s[i] != c) a1++; 37 } 38 39 min_cost = min(min_cost, a1 + dfs(l, mid, c + 1)); 40 41 return min_cost; 42 } 43 44 void solve() 45 { 46 int T; 47 cin >> T; 48 while(T--){ 49 cin >> len >> (s + 1); 50 cout << dfs(1, len, 'a') << endl; 51 52 } 53 } 54 55 int main() 56 { 57 ios::sync_with_stdio(false); 58 cin.tie(0); 59 cout.tie(0); 60 solve(); 61 62 return 0; 63 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17888.html
標籤：其他
上一篇：陣列中重復的數字