Educational Codeforces Round 57 (Rated for Div. 2) D dp

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

题意

给一个串s,删掉一个字符的代价为a[i],问使得s的子串不含"hard"的最小代价

题解

定义\(dp[i][j]\)为到第i位下一个将要匹配j的最小代价
- \(若s[i]==t[j]\)
  - 删掉:\(min(dp[i+1][j],dp[i][j]+a[i])\)
  - 不删,若j<3:\(min(dp[i+1][j+1],dp[i][j])\)
- \(若s[i]!=t[j]\)
  - 不用删:\(min(dp[i+1][j],dp[i][j])\)
\(ans=min(dp[n][i]),0 \leq i \leq 3\)

代码

#include<bits/stdc++.h>

#define ll long long

#define inf 0x3f3f3f3f

#define MAXN 100005

using namespace std;

ll dp[MAXN][4],a[MAXN],ans;

int n;string s;

int main(){

    cin>>n>>s;

    memset(dp,inf,sizeof(dp));

    for(int i=0;i<n;i++)scanf("%lld",&a[i]);

    string t="hard";

    dp[0][0]=0;

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

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

           if(dp[i][j]==inf)continue;

           if(s[i]==t[j]){

              dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[i]);

              if(j<3)dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);

           }else{

               dp[i+1][j]=min(dp[i+1][j],dp[i][j]);

           }

        }

    }

    ans=1e18;

    for(int i=0;i<4;i++)ans=min(ans,dp[n][i]);

    cout<<ans;

}

巴特西

Educational Codeforces Round 57 (Rated for Div. 2) D dp

题意

题解

代码

最新文章

热门文章