LittleElephantAndRGB

作者：梁浩

关键词：分类讨论，计数，递推

题意简述

给出一个长度为n的字符串S，其中只包含'R','G','B'三种字符，给出一个值m求有多少个四元组(a,b,c,d)满足$a\leq b,c\leq d,b<c$，且S[a..b]+S[c..d]中至少包含连续的m个'G'。 保证$m\leq n\leq 2500$.

算法

对每一个位置i，用dp[i][j]表示在该位置右边有多少个子串开头有至少j个连续的'G'，且不包含大于等于m个连续的'G'。以及f[i]表示有多少子串至少包含连续的m个'G'。
接下来，枚举a,b。如果该子串里有m个连续的'G'了，那它可以和其后所有子串构成合法四元组；如果它结尾处包含k个'G'的话，那他可以和b后所有开头包含至少m-k个'G'的子串以及所有包含m个连续'G'的子串构成合法四元组，即dp[b+1][m-k]+f[b+1]。
dp、f 数组可以从后向前递推得到。先设数组g[i][j]表示i后有多少子串开头包含恰好j个'G'且不包含连续m个'G'，那么dp就是g的前缀和。如果当前位置i后面最多可以有连续的k个'G'(k<m), 且i后第一个连续的m个'G'的结尾是x，那么g[i][k]=g[i+1][k]+x-i,g[i][j]=g[i+1]j,g[i][j]=g[i+1][j]+1(j&ltk)。f[i]=f[i+1]+n-x+1。 复杂度$O(n*m)$。