动态规划区间DP方法解决子串简写问题
本题分析:
例如: a b b a d a b d b a b c 求>=4个长度的以a开始b结尾的子串
求第一个a开头的个数 = 求 (0+3,n-1)区间中的b的个数
求第二个a开头的个数 = 求 (3+3,n-1)区间中的b的个数
以此类推,将他们叠加起来
显然,这不就是动态规划吗?
记得一定要开long long! 求累加累乘的问题一定要开long long!
#include <bits/stdc++.h>
using namespace std;
string str;
long long sum = 0;
long long DP[500020]; // 前n个数中含有b的个数(从零开始)
int main()
{
long long K;
cin >> K;
cin >> str;
char a,b;
cin >> a >> b;
// DP[i] = DP[i - 1] + ((str[i] == b) ? 1 : 0); 动态转移方程
if(str[0]==b)
DP[0] = 1;
long long n = str.size();
for(long long i=1;i<n;i++)
DP[i] = DP[i - 1] + ((str[i] == b) ? 1 : 0);
// 要求(i,n-1)区间的b的个数,就是求DP[n-1] - DP[i-1]
for(long long i=0;i+K-1<n;i++) // 时间复杂度为O(n) 注意看我循环条件
{
if(str[i]==a)//等于起始点i,开始计算i+K-1到n-1的b的个数
sum += DP[n-1] - DP[i+K-2];
}
cout << sum;
}