Codeforces 1096D Easy Problem 【DP】

时间：2022-09-09 09:55:14

<题目链接>

题目大意：

给你一个字符串，每个字符有权值，问现在删除字符串中的字符使其中没有"hard"的最小代价是多少。

解题分析：

用DP来求解：        转载于 >>>

dp[i][1]：表示字符串s的前i个字符中不含有前缀'h'的最小代价

dp[i][2]：表示字符串s的前i个字符中不含有前缀'ha'的最小代价

dp[i][3]：表示字符串s的前i个字符中不含有前缀'har'的最小代价

dp[i][4]：表示字符串s的前i个字符中不含有前缀'hard'的最小代价

对于状态转移，例如对dp[i][3]，如果位置i的字符不是r，那么dp[i][3] = dp[i - 1][3];
否则，要么去掉位置i的字符，则代价为dp[i - 1][3] + a[i]，如果不去除该位置字符，那么之前的序列不能含有'ha'，则代价为dp[i - 1][2]。

#include <bits/stdc++.h>

using namespace std;

#define N int(1e5+7)

typedef long long ll;

ll dp[N][],arr[N];

char s[N];

const ll INF = 1e18;

const char str[]="0hard";

int main(){

    int n;scanf("%d",&n);

    scanf("%s",s+);

    for(int i=;i<=n;i++)scanf("%d",&arr[i]);

    for(int i=;i<=n;i++)dp[i][]=INF;

    if(s[]=='h')dp[][]=arr[];

    for(int i=;i<=n;i++)

        for(int j=;j<=;j++){

            if(s[i]!=str[j])dp[i][j]=dp[i-][j];

            else dp[i][j]=min(dp[i-][j]+arr[i],dp[i-][j-]); //以j=3为例，dp[i-1][j]为前i-1项不含'har',并且去除第j项的'r'的代价(因为前i-1项可能包含'ha')，dp[i-1][j-1]表示前i-1项连'ha'都不包含

        }

    printf("%lld\n",dp[n][]);

}

一维的写法：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[];

char s[int(1e5+)];

const char ss[]="0hard";

int main(){

    int n;cin>>n;

    scanf("%s",s+);

    for(int i=;i<=n;i++){

        ll now;scanf("%lld",&now);

        if(s[i]=='h')dp[]+=now;

        for(int j=;j<=;j++)

            if(s[i]==ss[j])dp[j]=min(dp[j]+now,dp[j-]);

    }

    printf("%lld\n",dp[]);

}

2019-02-17

相关文章