Easy Problem ( CF-1096-D )

题目链接:https://codeforces.com/contest/1096/problem/D
题目大意:从一个字符串中删除若干个字母,使得字符串中不含hard(可以不连续但是先后次序要对),每个字母都有一个权值,问删掉的最少权值是多少
解题思路:dp,dp[i][0-3]分别代表在第i个状态下删h,删h或a,删h或a或r,删h或a或r或d的最少权值
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long dp[100010][10];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    char c[100010];
    cin>>c;
    int d;
    for(int i=1; i<=n; i++)
    {
        cin>>d;
        if(c[i-1]=='h')
        {
            dp[i][0]=dp[i-1][0]+d;
            dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
            dp[i][2]=min(dp[i-1][0],dp[i-1][2]);
            dp[i][3]=min(dp[i-1][0],dp[i-1][3]);
        }
        else if(c[i-1]=='a')
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1]+d;
            dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
            dp[i][3]=min(dp[i-1][1],dp[i-1][3]);
        }
        else if(c[i-1]=='r')
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1];
            dp[i][2]=dp[i-1][2]+d;
            dp[i][3]=min(dp[i-1][2],dp[i-1][3]);
        }
        else if(c[i-1]=='d')
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1];
            dp[i][2]=dp[i-1][2];
            dp[i][3]=dp[i-1][3]+d;
        }
        else
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1];
            dp[i][2]=dp[i-1][2];
            dp[i][3]=dp[i-1][3];
        }
    }
    cout<<min(min(dp[n][0],dp[n][1]),min(dp[n][2],dp[n][3]))<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注