伊埃斯的小站
日记

日记

Mon Dec 09 2024
6 分钟
life 日记
1365 字

虽然12月9号忘写了，但还是补一下吧。

上午#

昨天晚上打了 codeforces 诶您猜怎么着，那叫一个头昏脑胀（每周头昏脑胀 1/1145141/114514 ）于是先睡了 30min30min 。

P1613 跑路#

本来看到这题是一点思路都没有的，只知道是个dp。就连这个只知道是个dp都是由这玩意是在dp专题里才知道的。
然后一看题解：他就这么水灵灵的倍增上了？？
我们看：他说他每秒能走 2x2^x 。而他又要最快的去上班，因此，我们先想到要求最短路。但是一看 n≤50n \le 50 。这单源最短路时间复杂度也没那么高啊，肯定有鬼。一看：果然没那么简单。我们设有一条路径长度为 1616 ，而另一条路径长度却只有 77 。那么最短路算法肯定会找到 77 那条路径，但是实际上，77 要跳 33 次，因为 7=(111)(2)7 = (111)_{(2)}。但是 1616 只用跳一次，因为 16=(1000)(2)16 = (1000)_{(2)} 。而我们看这个 “一次能跳 2x2^x” ，就该想到倍增（？）
我们设 dpu,idp_{u,i} 表示从 uu 走 2i2^i 步到哪个点。然后又显然的转移 dpu,i=dpdpu,i−1,i−1dp_{u,i} = dp_{dp_{u,i - 1},i - 1} 。然后对于每一个 uu ，uu 到每一个 dpu,idp_{u,i} 都有一条长度为 11 的边，因为他能在一秒之内跳过去。就这样，我们建了一个图。而现在跑最短路就没有问题了。

下午#

CF1175E Minimal Segment Cover#

虽然这道题出现在dp专题里，但是它就像P1613 跑路一样，是个不怎么像dp的倍增。
还是那句话（实际上换了一句）：他就这么水灵灵的递增上了？？
我们设 dpi,jdp_{i,j} 表示从点 ii 覆盖 2j2^j 条线段最远能到的点，那么在输入线段 [l,r][l,r] 的时候，明显就有 dpl,0=max⁡(dpl,0,r)dp_{l,0} = \max(dp_{l,0},r) 因为可能有很多条 ll 相同的线段，所以要取 max⁡\max 。然后我们就可以转移：dpu,i=dpdpu,i−1,i−1dp_{u,i} = dp_{dp_{u,i - 1},i - 1} 。查询如下：

CPP
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 19; i >= 0; i--)
{
    if (dp[i][l] && dp[i][l] < r)//仿照lca，如果没到就跳
    {
        l = dp[i][l];
        cnt += (1 << i);
    }
}
if (dp[0][l] < r)//如果到不了就输出-1
    cout << "-1\n";
else
    cout << cnt + 1 << endl;//否则输出答案，因为没算最后一步，所以就要+1

P4342 Polygon
一看到这个，马上就想到断环成链，然后做区间dp。设 dp1l,rdp1_{l,r} 表示 [l,r][l,r] 区间内的运算最大值，那么有 dpl,r=max⁡k=lr−1dpl,kopdpk+1,rdp_{l,r} = \max\limits_{k = l}^{r - 1}dp_{l,k} \hspace{0.2cm} op \hspace{0.2cm} dp_{k + 1,r} 。但是我们发现有问题：加法里最大加最大一定是最大，但是乘法会有负负得正的情况，没准两个最小乘起来直接变最大。所以我们还要记录 dp2l,r=min⁡k=lr−1dpl,kopdpk+1,rdp2_{l,r} = \min\limits_{k = l}^{r - 1}dp_{l,k} \hspace{0.2cm} op \hspace{0.2cm} dp_{k + 1,r} 。然后，你觉得这样子就完了吗？远没有。因为有这个烦人的乘法，所以我们要考虑好多好多正负性。但是，我们看 dp1dp1 不是就记录最大值吗？dp2dp2 不就是一个最小值吗？那我们在乘法的时候把所有方案一起分别取一个最大值和最小值不就是了？那么就有：

dp1l,r={max⁡k=lr−1dp1i,k+dp1k+1,ropk=’t’max⁡k=lr−1(max⁡(max⁡(dp1i,k×dp1k+1,j,dp2i,k×dp2k+1,j),max⁡(dp1i,k×dp2k+1,j,dp2i,k×dp1k+1,j)))opk=’x’dp2l,r={min⁡k=lr−1dp1i,k+dp1k+1,ropk=’t’min⁡k=lr−1(min⁡(min⁡(dp1i,k×dp1k+1,j,dp2i,k×dp2k+1,j),min⁡(dp1i,k×dp2k+1,j,dp2i,k×dp1k+1,j)))opk=’x’dp1_{l,r} = \begin{cases} \max\limits_{k = l}^{r - 1}dp1_{i,k} + dp1_{k + 1,r} & op_k = \text{'t'} \\ \max\limits_{k = l}^{r - 1}(\max(\max(dp1_{i,k} \times dp1_{k + 1,j},dp2_{i,k} \times dp2_{k + 1,j}),\max(dp1_{i,k} \times dp2_{k + 1,j},dp2_{i,k} \times dp1_{k + 1,j}))) & op_k = \text{'x'} \end{cases} \\ dp2_{l,r} = \begin{cases} \min\limits_{k = l}^{r - 1}dp1_{i,k} + dp1_{k + 1,r} & op_k = \text{'t'} \\ \min\limits_{k = l}^{r - 1}(\min(\min(dp1_{i,k} \times dp1_{k + 1,j},dp2_{i,k} \times dp2_{k + 1,j}),\min(dp1_{i,k} \times dp2_{k + 1,j},dp2_{i,k} \times dp1_{k + 1,j}))) & op_k = \text{'x'} \end{cases}

也是又臭又长
然后就是区间dp的传统艺能：初始化 dp1i,i=dp2i,i=aidp1_{i,i} = dp2_{i,i} = a_i ，统计答案：ans=max⁡i=1ndpi,i+n−1ans = \max\limits_{i = 1}^{n}dp_{i,i + n - 1} 。注意要让它重复一遍，那样才能考虑环的情况。
然后这一题就这么打出来了。

晚上#

Mobile Service#

还是那句话：既然出现在dp题单里，那就一定是dp
我们做dp，先就是写出dp方程，什么时空复杂度待会再优化。我们设 dpi,x,y,zdp_{i,x,y,z} 为这三个工人分别在 x,y,zx,y,z 三个位置,正在处理第 ii 个请求的最小代价。然后我们发现，有转移：

dpi+1,pi+1,y,z=dpi,x,y,z+cx,pi+1dpi+1,x,pi+1,z=dpi,x,y,z+cy,pi+1dpi+1,x,y,pi+1=dpi,x,y,z+cz,pi+1dp_{i + 1,p_{i + 1},y,z} = dp_{i,x,y,z} + c_{x,p_{i + 1}} \\ dp_{i + 1,x,p_{i + 1},z} = dp_{i,x,y,z} + c_{y,p_{i + 1}} \\ dp_{i + 1,x,y,p_{i + 1}} = dp_{i,x,y,z} + c_{z,p_{i + 1}}

分别表示每一个工人去处理的情况。
但是，我们发现，总状态数是 2003×1000=8×109200^3 \times 1000 = 8 \times 10 ^ 9 。这不给你直接爆炸。
我们发现啊，当前一定有一个工人在处理当前的请求，那么我们就只用记录两个状态。现在我们的 dpi,x,ydp_{i,x,y} 表示有两个工人空闲且位置分别为 x,yx,y ，一个工人现在正在处理当前请求。那么有转移：

dpi+1,x,y=dpi,x,y+cpi,pi+1dpi+1,pi,y=dpi,x,y+cx,pi+1dpi+1,x,pi=dpi,x,y+cy,pi+1dp_{i + 1,x,y} = dp_{i,x,y} + c_{p_i,p_{i + 1}} \\ dp_{i + 1,p_i,y} = dp_{i,x,y} + c_{x,p_{i + 1}} \\ dp_{i + 1,x,p_i} = dp_{i,x,y} + c_{y,p_{i + 1}}

分别表示在当前请求位置的人去，xx 位置的人去，yy 位置的人去。
这样我们就得出了转移方程，总状态数只有 2002×1000=4×107200^2 \times 1000 = 4 \times 10^7 ，这样就爆不了了。