题解：P11456 [USACO24DEC] Interstellar Intervals G

· · 题解

教练讲了本题的线性做法，自己写一篇题解加深理解。

对于求方案数的问题，一般有两种方法解决。一是组合数学，二是动态规划。像本题这种序列问题，可以考虑动态规划。

设 f_i 表示前 i 个位置中，合法序列的方案数。

如果当前位置没有限制，则可以顺承上一个位置的方案数，即 f_i = f_{i-1}。如果当前位置有限制，那么找到一段前面的合法连续子段，记其左端点为 l，右端点为 r，则转移方程为 f_i = f_{i-1} + \sum_{j=l}^r f_j，显然可以用前缀和优化后面的一坨求和。

接下来考虑如何求左端点和右端点。统一对右端点进行操作，先预处理每个位置之前最晚出现的两种颜色下标，记为 prer 和 preb。在转移过程中假设当前下标为 i，能转移到 i 的下标为 j，那么右端点为 i - 2(i-j+1)，左端点为 preb_j，因为如果再往右就会到上上一个合法序列。

代码实现需要注意细节和特殊限制。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5e5+5;
const int p = 1e9+7;
int n,l,prer[N],preb[N];
ll f[N],sum[N];
vector<int> v[N];
string s;

ll cal(int now,int l,int r){
    int L=now-2*r,R=now-2*l;
    if(L>R) return 0;
    if(L<2) return sum[R];
    return (sum[R]-sum[L-2]+p)%p;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>s; l=s.size(),s=" "+s;   
    int lb=0,lr=0;
    for(int i=1;i<=n;i++){
        prer[i]=lr,preb[i]=lb;
        if(s[i]=='R') lr=i;
        if(s[i]=='B') lb=i;
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='X') v[i].push_back(i);
        if(s[i]=='B'){
            for(int j=i;j<=min(n,i*2-preb[i]-2);j++) //预处理j能被哪些i转移 
                v[j].push_back(i);
        }
    }
    sum[0]=f[0]=1;
    for(int i=1;i<=n;i++){
        if(s[i]!='R'){
            if(s[i]=='X') f[i]=f[i-1];
            int lim=i-prer[i]; //注意这里的限制 
            for(auto j:v[i]){
                int l=i-j+1;
                if(l>lim) continue;
                int r=min(lim,(i-preb[j])>>1);
                (f[i]+=cal(i,l,r))%=p;
            }
        }
        sum[i]=(i==1 ? f[1] : sum[i-2]+f[i])%p; //前缀和优化 
    }
    cout<<f[n];
    return 0;
}