T8 Easy Problem (CF1096D)

苹果蓝17 · 2020-04-03 15:18:13 · 个人记录

T8 Easy Problem (CF1096D)

CF传送门

洛谷传送门

题意简述

给你一个长为 n 的字符串以及 a_1...n ，删去第 i 个字符的代价为 a_i ，你可以删去一些字符，要求使得剩下的串中不含子序列 "hard"，求最小代价。 （子序列不需要连续）

数据范围

题解

思路

首先，显然答案只跟 h a r d 有关

其它字符就不用删也不用管了

接下来显然考虑dp

既然是子序列，不要求连续，就只跟相对位置有关

设想扫一遍，扫的过程中，hard是由har加上d得到的，而har是由ha加上r得到的

那不妨就以已经有了hard中的前几个字符为状态吧

显然是无后效性的

被动转移即可

做法

设 f[i][j] 表示前 i 个字符中，刚好凑成 hard 中前 j 个字符最小的代价

当前为r：f[2]->f[3], f[2]->f[2]+w[i]

当前为d：f[3]->f[4], f[3]->f[3]+w[i]

注意事项

· 答案是min(f[0],f[1],f[2],f[3])

· 开long long

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=100005;
long long n,f[5],w[N];
char s[N];
int main(){
    scanf("%lld\n",&n);
    for(long long i=1;i<=n;i++) scanf("%c",&s[i]);
    for(long long i=1;i<=n;i++) scanf("%d",&w[i]);
    for(long long i=1;i<=n;i++)
        switch(s[i]){
            case 'h':f[1]=min(f[0],f[1]),f[0]+=w[i];break;
            case 'a':f[2]=min(f[1],f[2]),f[1]+=w[i];break;
            case 'r':f[3]=min(f[2],f[3]),f[2]+=w[i];break;
            case 'd':f[4]=min(f[3],f[4]),f[3]+=w[i];break;
        }
    printf("%lld",min(f[0],min(f[1],min(f[2],f[3]))));
}