[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
上一篇: //指针的进一步理解
下一篇: 重金求子我不信