G - Cut Substrings

题目:

​ 给出两个字符串(s)(t),在(s)中删去(t),当字符串(s)不能再删去(t)的时候,请问最少的删除次数和方案数是多少。字符串长度为500。

思路:

​ 字符串长度为500,所以感觉可以乱搞。我们可以初步想到一个状态(f[i][j]),表示在(s)的前(i)个字符中,删了(j)次。这样好像还不够清晰地表达我们的状态,于是对其加一维,改为(f[i][j][0/1]),表示在(s)的前(i)个字符中,删了(j)次,0和1表示(i)是否是删去的开头。

图片

实现:

​ 初始化的话,(f[0][0][0] = 1),然后就是要特判一种情况,就是(t)长度大于(s),这样无法删去。从低到高枚举删去(t)的次数,第一个答案大于0的就是我们要的答案。值得一提的是,这样的写法理论上会被hack,当方案数恰好为(1e9+7)的时候,会被mod到0,但是感觉出题人并没有想到这一点。

#include <bits/stdc++.h>
    
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
#define SZ(x)    (int)x.size()
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
string yes = "Yesn"; string no = "Non";
const int mod = 1e9 + 7;

const int N = 505;
char s[N], t[N];
int f[N][N][2];
int can[N]; //可以被删去的位置

void solve()
{
    memset(f, 0, sizeof f);
    memset(can, 0, sizeof can);

    scanf("%s", s + 1);
    scanf("%s", t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);

    if(n < m)
    {
        printf("0 1n");
        return;
    }

    for(int i = 1; i <= n - m + 1; i ++)
    {
        bool ok = 1;
        for(int j = 1, k = i; j <= m; j ++, k ++)
        {
            if(s[k] != t[j])
                ok = false;
        }
        if(ok)  can[i + m - 1] = 1;
    }

    f[0][0][0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j <= n; j ++)
        {
            if(j > i)   continue;
            if(can[i])
            {
                if(j >= 1 && i - m >= 0)
                    f[i][j][1] = (f[i - m][j - 1][0] + f[i - m][j - 1][1]) % mod;
                for(int k = max(1, i - m + 1); k < i; k ++)
                    f[i][j][0] += f[k][j][1], f[i][j][0] %= mod;
            }
            else
                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mod;
        }
    }

    for(int i = 0; i <= n; i ++)
    {
        if((f[n][i][0] + f[n][i][1]) % mod > 0)
        {
            printf("%d %dn", i, (f[n][i][0] + f[n][i][1]) % mod);
            return;
        }
    }
}

signed main()
{
    int _ = 1;
    scanf("%d", &_);
    while(_--)
        solve();
}
内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/DM11/p/16700854.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!