fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  5. using namespace std;
  6.  
  7. const int N = 1e5 + 1;
  8. const int INF_LL = 1e18;
  9. int dp[N][4];
  10.  
  11. void solve() {
  12.     int n;
  13.     cin >> n;
  14.     string s;
  15.     cin >> s;
  16.     s = " " + s; // Thêm một khoảng trắng vào đầu chuỗi để dễ quản lý chỉ số
  17.     // Khởi tạo dp
  18.     for(int i = 0; i <= n; ++i) {
  19.         for(int j = 0; j <= 3; ++j) {
  20.             dp[i][j] = INF_LL; // Khởi tạo tất cả giá trị bằng INF_LL
  21.         }
  22.     }
  23.  
  24.     dp[0][0] = 0 ;
  25.  
  26.     for (int i = 1; i <= n; ++i) {
  27.         int x;
  28.         cin >> x;
  29.         if (s[i] == 'h') {
  30.             dp[i][0] = dp[i - 1][0] + x;
  31.             dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]);
  32.             dp[i][2] = dp[i - 1][2];
  33.             dp[i][3] = dp[i - 1][3];
  34.         } 
  35.         else if (s[i] == 'a') {
  36.             dp[i][0] = dp[i - 1][0];
  37.             dp[i][1] = dp[i - 1][1] + x;
  38.             dp[i][2] = min(dp[i - 1][2], dp[i - 1][1]);
  39.             dp[i][3] = dp[i - 1][3];
  40.         } 
  41.         else if (s[i] == 'r') {
  42.             dp[i][0] = dp[i - 1][0];
  43.             dp[i][1] = dp[i - 1][1];
  44.             dp[i][2] = dp[i - 1][2] + x;
  45.             dp[i][3] = min(dp[i - 1][3], dp[i - 1][2]);
  46.         } 
  47.         else if (s[i] == 'd') {
  48.             dp[i][0] = dp[i - 1][0];
  49.             dp[i][1] = dp[i - 1][1];
  50.             dp[i][2] = dp[i - 1][2];
  51.             dp[i][3] = dp[i - 1][3] + x;
  52.         }
  53.          else {
  54.             for (int j = 0; j <= 3; ++j) {
  55.                 dp[i][j] = dp[i - 1][j];
  56.             }
  57.         }
  58.     }
  59.     cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) << "\n";
  60. }
  61.  
  62. signed main() {
  63.     faster();
  64.     solve();
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
8
hhzarwde
3 2 6 9 4 8 7 1
stdout
copy 
4
https://ideone.com/pGKyGF
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!