jimmywang

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #[ZJOI2007]仓库建设#

首先山脚的那个一定得建。因为只能往山脚运，所以考虑从后往前dp dp[i]dp[i]dp[i]：在iii建一个仓库，后缀最小的值。所以 dp[i]=c[i]+j=i+1n(dp[j]+∑k=i+1j−1p[k]×(x[j]−x[k]) )dp[i]=c[i]+\min_{j=i+1}^...

C++ 动态规划

2021-10-15

0 482

题解 | #[SDOI2012]任务安排#

和P3628 [APIO2010]特别行动队差不多，都是序列拆成几个连续子段，每段都有一个权值，求权值最大/最小。于是如法炮制。 dp[i]:dp[i]:dp[i]:前iii个的总代价最小值。众所周知，后面的权值会被前面的决策影响。所以每次更新的时候加上如果这样决策后面的数增加的权值。于是...

C++ 动态规划

2021-10-15

0 439

题解 | #[NOIP2018]摆渡车#

观察到ttt很小，于是考虑在时间轴上dpdpdp。设c[i]c[i]c[i]为在iii时刻出发的人数。设dp[i]dp[i]dp[i]是在iii时刻出发，前iii分钟等待时间最少的值。所以 dp[i]=j=1i−mdp[j]+∑k=j+1i(i−k)∗c[k]dp[i]= \min_{j=1}...

C++ 动态规划

2021-10-15

0 543

题解 | #[SDOI2016]征途#

首先方差的式子： S2=1m∑i=1m(x‾−xi)2S^2=\dfrac{1}{m}\sum_{i=1}^{m}(\overline{x}-x_i)^2S2=m1∑i=1m(x−xi)2 =1m∑i=1mx‾2−2x‾xi+xi2=\dfrac{1}{m}\sum_{i=1}^{m}\ove...

C++ 动态规划

2021-10-15

0 376