记$S_{1}$和$S_{2}$分别为两个公司所拥有的站台集合，考虑当确定$S_{1}$和$S_{2}$后，如何求0到$n$的最短路
当最短路中从$i$走到$j$（其中$i>j$），那么一定有$j=i-1$，且下一次不会再向前走
（具体证明可以对其分类讨论，这里就省略了）
由此，即可做一个dp，用$f_{i,0/1}$表示仅考虑$0,1,...,i$这些点（的导出子图中），从0走到$i$之前最后一个属于$S_{1}$和属于$S_{2}$的点的最短路，转移即
$$
f_{i,0}=\begin{cases}f_{i-1,0}+1& (i\in S_{1},i-1\in S_{1})\\\min(f_{i-1,0},f_{i-1,1})+1&(i\in S_{1},i-1\in S_{2})\\\min(f_{i-1,0},f_{i-1,1}+2)&(i\in S_{2},i-1\in S_{1})\\f_{i-1,0}&(i\in S_{2},i-1\in S_{2})\end{cases}
$$
（以$f_{i,0}$为例，$f_{i,1}$类似）
最终，最短路即$\min(f_{n-1,0},f_{n-1,1})+1$
由于$f_{i,0/1}$仅通过$f_{i-1,0/1}$转移，可以记录这两个数，即令$F_{i,j,k,0/1}$表示仅考虑$0,1,...,i$，当前dp状态中$f_{i,0/1}$的值分别为$j$和$k$，以及最后第$i$个点属于$S_{1}$还是$S_{2}$，复杂度显然为$o(n^{3})$
构造$g_{i,0/1}$，其在相同的转移后令$g_{i,0}=\min(g_{i,0},g_{i,1}+2)$和$g_{i,1}=\min(g_{i,1},g_{i,0}+2)$
（注意$g_{i,0/1}$也是通过$g_{i-1,0/1}$转移，而不是$f_{i-1,0/1}$）
根据转移式子，不难归纳得到$g_{i,0}=\min(f_{i,0},f_{i,1}+2)$和$g_{i,1}=\min(f_{i,0}+2,f_{i,1})$
由此，也即有$\min(g_{n-1,0},g_{n-1,1})=\min(f_{n-1,0},f_{n-1,1})$，因此不妨重新定义$j$和$k$为$g_{i,0/1}$的值，不影响其正确性（当然在转移时也略有修改）
此时，有$|j-k|\le 2$，不妨记录$j$和$j-k+2$的值来描述$j$和$k$，复杂度即降为$o(n^{2})$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 4005
4 #define mod 1000000007
5 int n,m,ans,f[N][N][5][2];
6 char s[N];
7 int main(){
8 scanf("%d%d%s",&n,&m,s+1);
9 if (s[1]!='B')f[1][1][1][0]=1;
10 if (s[1]!='A')f[1][0][3][1]=1;
11 for(int i=2;i<n;i++)
12 for(int j=0;j<=n;j++)
13 for(int k=0;k<5;k++)
14 for(int p=0;p<2;p++){
15 if (s[i]!='B'){
16 int jj=j+1,kk=j+k-2;
17 if (p){
18 jj=min(j,j+k-2)+1;
19 kk=min(j+2,j+k-2);
20 }
21 int x=min(jj,kk+2),y=min(kk,jj+2);
22 f[i][x][y-x+2][0]=(f[i][x][y-x+2][0]+f[i-1][j][k][p])%mod;
23 }
24 if (s[i]!='A'){
25 int jj=j,kk=j+k-1;
26 if (!p){
27 jj=min(j,j+k);
28 kk=min(j,j+k-2)+1;
29 }
30 int x=min(jj,kk+2),y=min(kk,jj+2);
31 f[i][x][y-x+2][1]=(f[i][x][y-x+2][1]+f[i-1][j][k][p])%mod;
32 }
33 }
34 for(int i=0;i<=n;i++)
35 for(int j=0;j<5;j++)
36 if (min(i,i+j-2)+1<=m)ans=(ans+(f[n-1][i][j][0]+f[n-1][i][j][1])%mod)%mod;
37 printf("%d",ans);
38 }
View Code