CF1096D Easy Problem(DP)

제목: 문자열을 주고 i위의 비용을 a[i]로 빼고 문자열에 하드가 없는 최소한의 대가를 구합니다.
문제풀이: 이 문제의 사고방식은 비교적 체계적이다.
dp[i][kd] 2차원, kd=0은 d가 없는 최소 비용을 나타내고, 1은 rd가 없는 것을 나타내며, 2는 카드가 없는 것을 나타내고, 3은 하드가 없는 것을 나타낸다.
그렇다면 전이 방정식은 명백히 알 수 있다. 한마디로 앞에 없으면 나도 없으면 이 분만 꼭 가야 한다. 그렇지 않으면 갈 필요가 없다.
코드는 다음과 같습니다.
　　

#include
using namespace std;

int n,a[100010];
char s[100010];
long long dp[100010][4];

int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;i--)
    {
        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];
        if(s[i]=='d')
        {
            dp[i][0]=dp[i+1][0]+a[i];
            dp[i][1]=min(dp[i+1][0],dp[i+1][1]);
        } 
        if(s[i]=='r')
        {
            dp[i][1]=dp[i+1][1]+a[i];
            dp[i][2]=min(dp[i+1][1],dp[i+1][2]);
        }
        if(s[i]=='a')
        {
            dp[i][2]=dp[i+1][2]+a[i];
            dp[i][3]=min(dp[i+1][2],dp[i+1][3]);
        }
        if(s[i]=='h')
        {
            dp[i][3]=dp[i+1][3]+a[i];
        }
    }
    long long ans=0;
    ans=min(min(dp[1][0],dp[1][1]),min(dp[1][2],dp[1][3]));
    printf("%lld
",ans);
} #include
using namespace std;

int n,a[100010];
char s[100010];
long long dp[100010][4];

int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;i--)
    {
        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];
        if(s[i]=='d')
        {
            dp[i][0]=dp[i+1][0]+a[i];
            dp[i][1]=min(dp[i+1][0],dp[i+1][1]);
        } 
        if(s[i]=='r')
        {
            dp[i][1]=dp[i+1][1]+a[i];
            dp[i][2]=min(dp[i+1][1],dp[i+1][2]);
        }
        if(s[i]=='a')
        {
            dp[i][2]=dp[i+1][2]+a[i];
            dp[i][3]=min(dp[i+1][2],dp[i+1][3]);
        }
        if(s[i]=='h')
        {
            dp[i][3]=dp[i+1][3]+a[i];
        }
    }
    long long ans=0;
    ans=min(min(dp[1][0],dp[1][1]),min(dp[1][2],dp[1][3]));
    printf("%lld
",ans);
} 

 
전재 대상:https://www.cnblogs.com/stxy-ferryman/p/10344294.html