Codeforces Round#374 Div.2

A. One-dimensional Japanese Crossword

题意:给一个由黑白组成,大小为1×N的块,求所有黑的连续段

直接模拟即可


B. Passwords

题意:给N个字符串,然后告诉你其中的哪一个是正确的,你每次输入的字符串必须按照长度递增的顺序,长度相同可以按照任意方案,连续输入K次就会暂停5秒,问最快和最慢需要多少秒才能输到正确密码。

最快的是在相同长度中第一次就按到,最慢就是相同长度中最后一次按到

然后统计一发就没了,注意k的几个坑点


C. Journey

题意:给一张DAG,求1N的一条路径满足经过的点最多,总时间不超过T

考虑到DAG,我们很容易想到DAG上最短路的DP方法

然后我们不妨改一下,设dp[i,j]表示到达第i个城市,所经过的城市数为j的最小花费时间

那么我们就可以直接dp了,

dp[i,j]=min\begin{Bmatrix}dp[las,j-1]+w\end{Bmatrix}

注意要先循环j,我没循环导致wa了两次,这TM也能过样例也是醉了

输出方案只需要从N开始递归的向前走就可以

时间复杂度O(N\times M+N)


 

发表评论