洛谷 CF894A QAQ
程序员文章站
2022-03-20 22:22:10
[TOC] 题目 "CF894A" 思路 $\text{DP}$ 一个数组$\text{QAQ[4][101]}$ $\text{QAQ[1][i]表示在i这个位置q的个数}$ $\text{QAQ[2][i]表示在i这个位置qa的个数}$ $\text{QAQ[3][i]表示在i这个位置能形成QA ......
目录
题目
思路
$\text{dp}$
一个数组$\text{qaq[4][101]}$
$\text{qaq[1][i]表示在i这个位置q的个数}$
$\text{qaq[2][i]表示在i这个位置qa的个数}$
$\text{qaq[3][i]表示在i这个位置能形成qaq的个数}$
对于第$i$个位置的$q$
可以组成$\text{qaq[2][i]}$个$qaq$
所以$\text{qaq[3][i]+=qaq[2][i]}$
对于第$i$个位置的$a$
可以组成$\text{qaq[1][i]}$个$qa$
所以$\text{qaq[2][i]+=qaq[1][i]}$
$code$
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> using namespace std; string s; int qaq[4][101]; //qaq[1][i]表示在i这个位置q的个数 //qaq[2][i]表示在i这个位置qa的个数 //qaq[3][i]表示在这个位置能形成qaq的个数 inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } int main(){ cin>>s; int ns=s.length(); for(int i=0;i<ns;++i){ if(i!=0){ qaq[1][i]=qaq[1][i-1]; qaq[2][i]=qaq[2][i-1]; qaq[3][i]=qaq[3][i-1]; } if(s[i]=='q'){ qaq[1][i]++; qaq[3][i]+=qaq[2][i]; } if(s[i]=='a'){ qaq[2][i]+=qaq[1][i]; } } cout<<qaq[3][ns-1]; return 0; }
上一篇: 详解Lua中的数组概念知识
下一篇: 编程范式--对象范式,这不是原来的配方了