门户网站的建设公司,教育行业网站建设审批,ppt模板免费下载网站不需要登录,北京网站定制题目大意#xff1a;
现在有一个由小写字母组成的字符串#xff0c;去掉这个字符串的第i个位置的字符会有ai的代价。你的任务是去掉这个字符串中的一些字符使得该字符串中不包含子序列hard#xff0c;且去掉字符的代价之和尽可能小。
输入
第一行一个整数n表示字符串的长…题目大意
现在有一个由小写字母组成的字符串去掉这个字符串的第i个位置的字符会有ai的代价。你的任务是去掉这个字符串中的一些字符使得该字符串中不包含子序列hard且去掉字符的代价之和尽可能小。
输入
第一行一个整数n表示字符串的长度(1n100000)。 第二行一个给定的字符串。 第三行n个整数a1,a2,a3,...,an(1ai998244353)。
输出
输出一个整数表示答案。
Examples
Input
6
hhardh
3 2 9 11 7 1Output
5Input
8
hhzarwde
3 2 6 9 4 8 7 1Output
4Input
6
hhaarr
1 2 3 4 5 6Output
0Note
In the first example, first two characters are removed so the result is ardh.
In the second example, 55-th character is removed so the result is hhzawde.
In the third example theres no need to remove anything.
解题报告
考虑dp。首先有效字符只有hard四个字符考虑转移。
如果出现不合法序列最后一个字符肯定是d并且前面按照顺序出现了har所以可以设定dp[n][4]代表前缀不出现h不出现ha不出现har不出现hard的最小代价。最后dp[n][4]就是答案。
转移就是对于四个字符中的每一个字符假设是d那么更新dp[i][4]则选择删除或者不删除这个字符如果删除则从dp[i-1][4]a[i]转移过来如果不删除则需要保证前i-1个字符不能有har所以dp[i-1][3]转移过来。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
char s[MAX];
int n,a[MAX];
ll dp[MAX][5];//h a r d
int main()
{memset(dp,0x3f,sizeof dp);for(int j 1; j4; j) dp[0][j] 0; cin n;cin s1;for(int i 1; in; i) cin a[i];for(int i 1; in; i) {for(int j 1; j4; j) dp[i][j] dp[i-1][j];if(s[i] h) dp[i][1] dp[i-1][1]a[i];if(s[i] a) dp[i][2] min(dp[i-1][2]a[i],dp[i-1][1]);if(s[i] r) dp[i][3] min(dp[i-1][3]a[i],dp[i-1][2]);if(s[i] d) dp[i][4] min(dp[i-1][4]a[i],dp[i-1][3]);}printf(%lld\n,*min_element(dp[n]1,dp[n]5));return 0 ;
}
