sacgajcvs

Untitled

Nov 13th, 2020
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.80 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. #define N 100005
  5.  
  6. ll dp[N][2];
  7. ll c1, c2, n;
  8. string s;
  9.  
  10. ll fun(ll i, bool f) {
  11. if(i == n) {
  12. return 0;
  13. }
  14. ll& ans = dp[i][f];
  15. if(ans != -1) {
  16. return ans;
  17. }
  18. if(f) {
  19. if(s[i] == 'B') {
  20. ans = min(fun(i + 1, 1) + c2, fun(i + 1, 0));
  21. } else {
  22. ans = fun(i + 1, 1);
  23. }
  24. } else {
  25. if(s[i] == 'B') {
  26. ans = fun(i + 1, 0);
  27. } else {
  28. ans = fun(i + 1, 1) + c1;
  29. }
  30. }
  31. return ans;
  32. }
  33.  
  34.  
  35. void solve()
  36. {
  37. cin >> c1 >> c2 >> s;
  38. n = s.length();
  39. for(int i = 0; i <= n; i++) {
  40. for(int j = 0; j < 2; j++) {
  41. dp[i][j] = -1;
  42. }
  43. }
  44. ll ans;
  45. if(s[0] == 'W') {
  46. ans = fun(1,1) + c1;
  47. } else {
  48. ans = fun(1,0);
  49. }
  50. cout << ans << endl;
  51. return;
  52. }
  53. int main()
  54. {
  55. int TESTS=1;
  56. cin >> TESTS;
  57. while(TESTS -- )
  58. {
  59. solve();
  60. }
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment