您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

1040 有几个PAT (25 分)

不牌不改 发布时间:2022-03-28 20:04:59 ,浏览量:0

题目

题目链接

题解

动态规划。

f[i][j]表示前i个字符中构成PAT中前j个字符构成字符串的个数,其实就是f[i][1]表示前i个字符构成P的个数,f[i][2]表示前i个字符构成PA的个数,f[i][3]表示前i个字符构成PAT的个数。

状态转移,以更新f[i][2]为例子,如果s[i]==A,那么前i-1个字符构成P后加上这个A就可以得到PA,这样得到的PA个数为前i-1个字符构成P的个数,即f[i-1][P]=f[i-1][1],这些是新构成的,因为使用了新的字符s[i],还有之前就已经构成的PA,这些的个数为f[i-1][PA] = f[i-1][2],故前i个字符构成PA的个数等于前i-1个字符构成P的个数+前i-1个字符构成PA的个数=f[i-1][1] + f[i-1][2];如果s[i]!=A,那么不会有新增加的PA,所以f[i][2]=f[i-1][2]

初始化,因为当s[i]==P时,需要计算f[i][1] = 1 + f[i-1][1],即前i-1个字符构成空串的个数+前i-1个字符构成P的个数,为了方便将f[0][0]初始化为1后,在递推更新的过程中f[i][0]都会被设置为1,这样f[i][1]更新也可以与其他两个通用一个转移方程了。

其实这个题很简单,但是不知道为什么一遇到动态规划就想记录一下。

代码
#include
using namespace std;
const int N = 1e5+10, MOD = 1000000007;
int f[N][4]; // 前i个字符构成 空,P,PA,PAT 的个数 
map  mp = {{'P', 1}, {'A', 2}, {'T', 3}};
string s;
int main()
{
	cin >> s;
	int n = s.size();
	s = '.' + s;
	f[0][0] = 1;
	for (int i = 1;i             
关注
打赏
1662186765
查看更多评论
0.0352s