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

CodeForces - 1426F Number of Subsequences(dp)

程序员文章站 2022-06-19 10:04:23
题目链接:点击查看题目大意:给出一个长度为 n 的字符串,由 ' a ' , ' b ' , ' c ' 和 ' ? ' 组成,每一个 ' ? ' 都可以变成三个字母之一,这样的话假设有 k 个 ' ? ' ,则整个字符串就有 3^k 中不同的表示,现在问这 3^k 个字符串中,一共有多少个 abc 的子序列(不需要连续)题目分析:考虑 dp,如果没有 ' ? ' 的话还是比较经典的一道 dp 题目,dp[ i ][ 0 ] 代表的是到了第 i 个位置时,' a ' 子序列的个数,dp[ i ][....

题目链接:点击查看

题目大意:给出一个长度为 n 的字符串,由 ' a ' , ' b ' , ' c ' 和 ' ? ' 组成,每一个 ' ? ' 都可以变成三个字母之一,这样的话假设有 k 个 ' ? ' ,则整个字符串就有 3^k 中不同的表示,现在问这 3^k 个字符串中,一共有多少个 abc 的子序列(不需要连续)

题目分析:考虑 dp,如果没有 ' ? ' 的话还是比较经典的一道 dp 题目,dp[ i ][ 0 ] 代表的是到了第 i 个位置时, ' a ' 子序列的个数,dp[ i ][ 1 ] 代表的是到了第 i 个位置时,' ab ' 子序列的个数,dp[ i ][ 2 ] 代表的是到了第 i 个位置时,' abc ' 子序列的个数,答案显然就是 dp[ n ][ 2 ] 了

考虑 ' ? ' 会对 dp 的转移产生什么影响,因为 ' ? ' 可以将三种字母全部都表示一遍,所以到了第 i 个位置时,如果前面有 x 个 ' ? ' 的话,那么到达此位置的字符串就会有 3^x 种,如果不考虑 ' ? ' 的话,碰到一个 ' a ' ,dp[ i ][ 0 ] 就需要加一,但现在如果考虑到 ' ? ' 的影响,dp[ i ][ 0 ] 就需要加上 3^x 才行

再考虑用 ' ? ' 去分别表示三种字母:

  1. ' ? ' 表示 ' a ' :前面仍然有 dp[ i - 1 ][ 0 ] 个 ' a ',仍然有 dp[ i - 1 ][ 1 ] 个 ' ab ',仍然有 dp[ i - 1 ][ 2 ] 个 ' abc ',多了 3^x 个 a
  2. ' ? ' 表示 ' b ' :前面仍然有 dp[ i - 1 ][ 0 ] 个 ' a ',仍然有 dp[ i - 1 ][ 1 ] 个 ' ab ',仍然有 dp[ i - 1 ][ 2 ] 个 ' abc ',多了 dp[ i - 1 ][ 0 ] 个 b
  3. ' ? ' 表示 ' c ' :前面仍然有 dp[ i - 1 ][ 0 ] 个 ' a ',仍然有 dp[ i - 1 ][ 1 ] 个 ' ab ',仍然有 dp[ i - 1 ][ 2 ] 个 ' abc ',多了 dp[ i - 1 ][ 1 ] 个 c

直接转移就好了

代码:

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map> 
using namespace std;
      
typedef long long LL;
      
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;

const int N=2e5+100;

const int mod=1e9+7;

LL dp[N][3];

char s[N];

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n;
	scanf("%d%s",&n,s+1);
	LL base=1;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='a')
		{
			dp[i][0]=(dp[i-1][0]+base)%mod;
			dp[i][1]=dp[i-1][1];
			dp[i][2]=dp[i-1][2];
		}
		else if(s[i]=='b')
		{
			dp[i][0]=dp[i-1][0];
			dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod;
			dp[i][2]=dp[i-1][2];
		}
		else if(s[i]=='c')
		{
			dp[i][0]=dp[i-1][0];
			dp[i][1]=dp[i-1][1];
			dp[i][2]=(dp[i-1][1]+dp[i-1][2])%mod;
		}
		else if(s[i]=='?')
		{
			dp[i][0]=(dp[i-1][0]*3+base)%mod;
			dp[i][1]=(dp[i-1][1]*3+dp[i-1][0])%mod;
			dp[i][2]=(dp[i-1][2]*3+dp[i-1][1])%mod;
			base=base*3%mod;
		}
	}
	printf("%lld\n",dp[n][2]);















   return 0;
}

 

本文地址:https://blog.csdn.net/qq_45458915/article/details/108859787