欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

[PAT*]1025 Keep at Most 100 Characters (35分)

程序员文章站 2022-03-07 16:33:37
分析:dp[i][j]表示考虑前i位,能够得到的长度为j的串的数量,dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]dp[i - 1][j - 1]代表了以s[i]结尾的长度为j的个数,显然跟dp[i - 1][j]有重合的部分,也就是dp[i - 1][j]中以s[i]结尾的长度为j的个数,所以只需要把这部分扣除就可,用last[]记录s[i]最近出现的位置。初始化:每次初始化dp[i][1] = dp[i - 1][1] + !(s[i]之前是否出现过)代码...

分析:

dp[i][j]表示考虑前i位,能够得到的长度为j的串的数量,
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
dp[i - 1][j - 1]代表了以s[i]结尾的长度为j的个数,显然跟dp[i - 1][j]有重合的部分,也就是dp[i - 1][j]中以s[i]结尾的长度为j的个数,所以只需要把这部分扣除就可,用last[]记录s[i]最近出现的位置。
初始化:每次初始化dp[i][1] = dp[i - 1][1] + !(s[i]之前是否出现过)

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
ll dp[1010][110];
int last[30];

int main()
{
    char s[1010]; cin >> (s + 1);
    int n = strlen(s + 1);
    for(int i = 1; i <= n; i++)
    {
        int pos = last[s[i] - 'a'];
        dp[i][1] = dp[i - 1][1] + !pos;
        for(int j = 2; j <= min(i, 100); j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - (pos ? dp[pos - 1][j - 1] : 0);
            dp[i][j] = (dp[i][j] % mod + mod) % mod;
        }
        last[s[i] - 'a'] = i;
    }
    ll res = 0;
    for(int i = 1; i <= min(n, 100); i++)
        res = (res + dp[n][i]) % mod;
    cout << res << endl;

}

本文地址:https://blog.csdn.net/weixin_43987810/article/details/107531233

相关标签: PAT*