[ARC119F] AtCoder Express 3

本文主要是介绍[ARC119F] AtCoder Express 3，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

[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;
}

这篇关于[ARC119F] AtCoder Express 3的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程