GYM102785J. R u really ready?

题目链接:https://codeforces.com/gym/102785/problem/J

很简单的 dp 模型,dp_{i,j} 表示 a[1…i]b[1..j] ;是否能匹配,能匹配为 1 ,否则为 0

然后把所有的 + 转换成 * ,加一个字母就行

dp的过程就是分类讨论,根据题目 * 的含义推就好。。。

没做出来真不应该。。好惭愧。。想了想是因为ACM以来就没做过双字符串,设计dp[n][m],这样经典的dp模型了

#include<bits/stdc++.h>
using namespace std;
const int N = 3020;
char s[N],a[N],b[N];
int n,m,t;
int dp[N][N];
int main(){
    scanf(" %s",s+1);
    scanf(" %s",b+1);
    t=strlen(s+1);
    m=strlen(b+1);
    for(int i=1;i<=t;++i){
        if(s[i]=='+') {char p=a[n];a[++n]=p;a[++n]='*';}
        else a[++n]=s[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        if(a[i]=='*')
            dp[i][0]|=dp[i-2][0];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i]=='*') dp[i][j]=dp[i-2][j]|dp[i-1][j]|(a[i-1]==b[j]&(dp[i][j-1]));
            else dp[i][j]=(dp[i-1][j-1]&(a[i]==b[j]));
        }
    }
    puts(dp[n][m]?"Yes":"No");
    return 0;
}
分类: DP

0 条评论

发表评论

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