Codeforces 1096D (DP)

Codeforces 1095F
题意：给定字符串$s$，每个位有一个权值，删掉一个位代价为这个权值。请求出最小使得字符串不包含子序列hard的代价。

最优化问题想到DP，并且这题类似于 Bzoj 1030 AC自动机。
这里是一个匹配类状态的 DP，设$dp(i,j)$为前$i$位，$j=0$表示没有匹配，$j=[1,3]$表示匹配到了前缀h, ha, har的最小代价。

转移则

dp[0][0] = 0;
for (LL j = 0; j < 4; ++j) dp[i][j] = dp[i - 1][j];
for (LL i = 1; i <= n; ++i) {
  if (s[i] == 'h') {
      dp[i][0] = dp[i - 1][0] + a[i]; //  将 `h` 删去
      dp[i][1] = min(min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][1] + a[i]); // 不动或者将 `h` 删去
  }
  if (s[i] == 'a') {
      dp[i][1] = dp[i - 1][1] + a[i]; //  将 `a` 删去
      dp[i][2] = min(min(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][2] + a[i]); // 不动或者将 `a` 删去
  }
  if (s[i] == 'r') {
      dp[i][2] = dp[i - 1][2] + a[i]; //  将 `r` 删去
      dp[i][3] = min(min(dp[i - 1][2], dp[i - 1][3]), dp[i - 1][3] + a[i]); // 不动或者将 `r` 删去
  }
  if (s[i] == 'd') {
      dp[i][3] = dp[i - 1][3] + a[i]; //  将 `d` 删去
  }
}

其实中间转移不需要dp[i - 1][3], dp[i - 1][3] + a[i]，因为$a_i \geq 0$，所以直接写即可。

知识点：
1、匹配类状态的 DP

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, a[100000 + 5], dp[100000 + 5][5], INF = 4223372036854775808ll;
    char s[100000 + 5];

    void clean() {
    }
    int solve() {
        clean();
        cin >> n;
        scanf("%s", s + 1);
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]);

        for (LL i = 0; i <= n; ++i)
        for (LL j = 0; j < 5; ++j) dp[i][j] = INF;
        dp[0][0] = 0;

        for (LL i = 1; i <= n; ++i) {
            for (LL j = 0; j < 4; ++j) dp[i][j] = dp[i - 1][j];
            if (s[i] == 'h') {
                dp[i][0] = dp[i - 1][0] + a[i];
                //dp[i][1] = min(min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][1] + a[i]);
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);
            }
            if (s[i] == 'a') {
                dp[i][1] = dp[i - 1][1] + a[i];
                //dp[i][2] = min(min(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][2] + a[i]);
                dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]);
            }
            if (s[i] == 'r') {
                dp[i][2] = dp[i - 1][2] + a[i];
                //dp[i][3] = min(min(dp[i - 1][2], dp[i - 1][3]), dp[i - 1][3] + a[i]);
                dp[i][3] = min(dp[i - 1][2], dp[i - 1][3]);
            }
            if (s[i] == 'd') {
                dp[i][3] = dp[i - 1][3] + a[i];
            }
        }
        printf("%lld", min(min(dp[n][0], dp[n][1]), min(dp[n][2], dp[n][3])));
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}