[ARC119F]AtCoder Express 3

记$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})$,可以通过

[ARC119F]AtCoder Express 3
 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

 

上一篇:webhook


下一篇:atcoder-ABC202-E