cfedu57D

链接

http://codeforces.com/contest/1096/problem/D

题意

给你一个长度为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]
        ...

博主蒟蒻可以随意转载但要附上本文链接广告位招租