本文主要是介绍1093 Count PAT's (25 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一道简单动态规划的题
没想到转眼间就3月1号了，我昨天还想着2月剩下的几天可以把这个月的原创数量增加到70呢，结果临睡前才发现3月已经到来了。
#include<cstdio>
#include<cstring>
int main(){const int maxn=1e5+5;char str[maxn];int dp[maxn],dt[maxn];scanf("%s",str);memset(dp,0,sizeof(dp));memset(dt,0,sizeof(dt));int len = strlen(str);for(int i=0;i<len;i++){if(i==0){if(str[i]=='P') dp[i]=1;else dp[i]=0;if(str[len-1-i]=='T') dt[len-1-i]=1;else dt[len-1-i]=0;}else{if(str[i]=='P') dp[i]=dp[i-1]+1;else dp[i]=dp[i-1];if(str[len-1-i]=='T') dt[len-1-i]=dt[len-i]+1;else dt[len-1-i] = dt[len-i];} }long long res=0;for(int i=0;i<len;i++){if(str[i]=='A'){res= (res + dp[i]*dt[i]) % 1000000007;}}printf("%lld",res);return 0;
}
这篇关于1093 Count PAT's (25 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
