[ARC119F] AtCoder Express 3
题目大意
一条铁路共 \(N+1\) 个站点，从左到右以 \(0\) 到 \(N\) 标号，对每一个 \(i\; (0\le i\le N-1)\)，\(i\) 号车站与 \(i+1\) 号车站有一条双向铁路。
每个站点可能属于 A 类或 B 类，最近的同类车站间也会有一条双向铁路。\(0\) 号和 \(N\) 号站点可以看做既属于 A 类又属于 B 类。
现给出已经确定的每一个车站的类型，对剩下所有未确定的车站进行分类，求有多少种分类方式使得从 \(0\) 到 \(N\) 可以只经过不超过 \(K\) 条铁路\(\pmod{10^9+7}\)。
思路
先考虑车站类型确定的时候如何算最短路。
由于有可能会出现为了到达连通块右端点，先利用另一种颜色跳过一大段同色站再回退一站的情况，状态需要特殊处理。
记 \(f_{i,0/1}\) 表示只考虑 \(1\sim i\) 的车站，从起点到左边至端点 \(i\) 最近的一个 A/B 站的最短路。以 \(f_{i,0}\) 为例，转移如下（\(f_{i,1}\) 同理）。
\[f_{i,0}= \begin{cases} f_{i-1,0}+1&(c_i=A,c_{i-1}=A)\\ \min(f_{i-1,0},f_{i-1,1})+1&(c_i=A,c_{i-1}=B)\\ \min(f_{i-1,0},f_{i-1,1}+2)&(c_i=B,c_{i-1}=A)\\ f_{i-1,0}&(c_i=B,c_{i-1}=B) \end{cases} \]记 \(F_{i,j,k,0/1}\) 表示只考虑 \(1\sim i\) 的车站，\(f_{i,0}=j\)，\(f_{i,1}=k\)，且 \(c_i=A/B\) 的方案。
此时时间复杂度为 \(O(n^3)\)。
考虑优化，注意到很多状态其实上是无用的。即对于之前说的后面更新前面（第三个转移）的情况，如果 \(f_{i-1,0}\) 远大于 \(f_{i-1,1}\)，最后遇到一个 B 或者到了终点一定会选择由 \(f_{i-1,1}\) 转移过来。
而遇到一个 B 或是终点是必然的。因此当 \(f_{i,0}>f_{i,1}+2\) 时，直接将 \(f_{i,0}:=f_{i,1}+2\) 是不会有问题的，相反对 \(f_{i,1}\) 同理。
此时 \(f_{i,0/1}\) 的意义就变成了：从起点到左边至端点 \(i\) 最近的一个 A/B 站，或是 \(i\) 所在同色连通块的右端点的车站（当 \(i\) 此时与状态中颜色相异时无此意义）的最短路。
这样可以保证 \(|j-k|\le 2\)，时间复杂度降为 \(O(n^2)\)。
代码
点击查看代码
#include<bits/stdc++.h>
#define I inline
#define R register int
#define ll long long
using namespace std;
const int N=4005,M=2005,P=1e9+7;
I void pls(int &a,const int &b){a+=b;if(a>=P)a-=P;}
I int add(const int &a,const int &b){return a+b>=P?a+b-P:a+b;}
char s[N];
int f[N][M][5][2];
int main()
{
int n,m;
scanf("%d%d%s",&n,&m,s+1);--n;--m;
if(s[1]!='B')f[1][1][1][0]=1;
if(s[1]!='A')f[1][0][3][1]=1;
for(R i=2;i<=n;i++)
for(R j=0;j<=m+2;j++)
for(R a=0,w=j-2,x,y;a<=4&&w<=m+2;a++,w++)
{
const int *p=f[i-1][j][a];
if(!p[0]&&!p[1])continue;
if(s[i]!='B')
{
y=w;x=min(j+1,y+2);
if(min(x,y)<=m)pls(f[i][x][y-x+2][0],p[0]);
y=min(w,j+2);x=min(min(j,w)+1,y+2);
if(min(x,y)<=m)pls(f[i][x][y-x+2][0],p[1]);
}
if(s[i]!='A')
{
x=j;y=min(w+1,x+2);
if(min(x,y)<=m)pls(f[i][x][y-x+2][1],p[1]);
x=min(j,w+2);y=min(min(w,j)+1,x+2);
if(min(x,y)<=m)pls(f[i][x][y-x+2][1],p[0]);
}
}
int ans=0;
for(R j=0;j<=m+2;j++)
for(R a=0,w=j-2;a<=4&&w<=m+2;a++,w++)
{
if(w<0)continue;
if(min(j,w)<=m)pls(ans,add(f[n][j][a][0],f[n][j][a][1]));
}
printf("%d\n",ans);
return 0;
}