目录
题意：
给定一个长度为n的字符串，每次不能选择相邻的字符，求子序列个数。
1 < = n < = 2 e 5
思路
比较容易想到的d p状态为:d p [ i ]表示从[ 1 , i ]中选并且s [ i ]必选的方案数
转移为d p [ i ] = ∑ j = 0 i − 1 d p [ j ];
这样很容易会造成计数重复，比如a b a c b a，当枚举到最后一个a的时候，可以跟第一个a组成a a，也可以跟第三个a组成a a。
会发现只需要维护到离i最近的最大的j就可以了，记为k。因为k之前的子序列想要用s i的话，就可以用s k替代，这样就不会重复了。
转移为d p [ i ] = ∑ j = 0 k d p [ j ];
如果k = = 0的话，说明前面没有相同的字符，从起始开始转移就好了；
时间复杂度：看起来感觉是O ( n 2 )的，但最多只有26种字母，所以第二层循环最多枚举到26，时间复杂度O ( 26 n )
再来考虑本题，加上了不能选相邻条件的限制，只需要算的时候将答案向后平移即可：
d p [ i + 2 ] = ∑ j = i j > = k d p [ j ]
实现起来有很多细节
比如转移方程是将d p [ i ]的答案累加到了d p [ i + 2 ]上，计算答案的时候要从2到n + 1，相当于整体向后平移
由于j = = i的时候一定符合题意(选i和i + 2)，所以判断跳出循环的条件是在计算更新答案之后的，就要注意条件的判断了；
j = = 0的时候说明到达字符串的开始位置了；s [ j − 1 ] = = s [ i ]说明下一位两个字符相同，也就是j − 1 = = k，可以跳出了。
代码：
// Problem: F - Substrings // Contest: AtCoder - AtCoder Beginner Contest 214 // URL: https://atcoder.jp/contests/abc214/tasks/abc214_f // Memory Limit: 1024 MB // Time Limit: 2000 ms // Author:Cutele // // Powered by CP Editor (https://cpeditor.org) //#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=2e5+7,mod=1e9+7; int dp[maxn],n; int main(){ string s;cin>>s; n=s.size(); dp[0]=1; for(int i=0;i<n;i++) for(int j=i;;j--){ dp[i+2]=(dp[i+2]+dp[j])%mod; if(s[j-1]==s[i]) break; if(j==0) break; } ll ans=0; rep(i,2,n+1) ans=(ans+dp[i])%mod; write(ans); return 0; }
![P2881 [USACO07MAR]Ranking the Cows G](https://ucc.alicdn.com/pic/developer-ecology/55acef05da9d4e6cadcc9a235af3fec8.png?x-oss-process=image/resize,h_160,m_lfit)
