转移自老blog

cfedu57D

链接

题意

        给你一个长度为n的字符串，每个点有一个删除的代价，问让字符串中不存在子序列hard的最小删除代价。
        1<=n<=1e5

题解

        设:
        dp[i][0] 前缀i不包含子序列h的最小代价
        dp[i][1] 前缀i不包含子序列ha的最小代价
        dp[i][2] 前缀i不包含子序列har的最小代价
        dp[i][3] 前缀i不包含子序列hard的最小代价
        当碰到h的时候，会影响dp[i-1][0]   若删除   转移到dp[i][0]   若不删除   转移到dp[i][1]
        当碰到a的时候，会影响dp[i-1][1]   若删除   转移到dp[i][1]   若不删除   转移到dp[i][2]
        ...