【HNOI2010】公交线路

搞了一个上午就搞出这一个题

还是看了题解的

不过还是看懂了。。而且自认为我比标程写的好懂些(事实上我都没看懂标程最后在干嘛)

首先观察数据范围:109,显然得用O(n)以下复杂度的方法

那么就是什么logn了

一开始觉得是组合数学问题,然而发现并不能做

于是好像只有一种方法了:递推+矩阵快速幂

然而状态似乎不是很好搞。。

根据题解+用草稿纸推了半天。。。

———————————————————————————-

。。。。算了直接讲正解

首先定义状态dp[i][s]为走到第i位,状态为s的方案数

状态s的定义为每辆车到该点的距离的无序集合(可重复)

比如每辆车到这个点的距离分别为3,2,0,4

那么s为{0,2,3,4}

再证明一下:因为相邻站台有距离限制,所以s中的数只可能为[0,P)

并且因为该点所属车到该点的距离为0,所以s中必定有一个0

所以不同的s最多有max{C(p-1,k-1)}=C(9,5)=126种,就可以状态压缩了。

在定义一个矩阵m,当第i种状态能转移为第j种状态时m[i][j]=1,否则为0

规定第1种状态为{0,1,2,3…k-1},那么dp[k][1]=1(每辆车都在始发站中),dp[i]=dp[i-1]*m

矩阵快速幂,最终答案为dp[n][1](每辆车都在终点站中)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz