啊对对对，下次题解写详细一点好不好。
首先考虑 naive 的 \(O(n^2)\)，记 \(dp[i][j]\) 表示从 \(1\) 走到 \(i\)，恰好走了 \(j\) 条黑边的时候走过白边的最少数量。
\(O(nm)\) 转移，\(O(nq)\) 询问，十分 naive 且显然过不去。
这个时候我们固定一个 \(i\)，然后把所有 \((j,dp[i][j])\) 扔到坐标系上，那么有以下两个结论：
- 最优的点在凸包上。
显然，因为询问相当于是求 \(\min_{j}(A\times j+B \times dp[i][j])\)，扔到坐标系上以后每个点都在一条 \(Ax+By=k\) 的直线上，类比一下斜率优化，画个图感性理解一下，最优的点确实一定在凸包上。
- 凸包上的点数是 \(O(n^{\frac{2}{3}})\) 的。
经典结论（我不会证）：在 \(n \times n\) 的网格（意味着点是整点）中撒点，凸包上点数最多是 \(O(n^{\frac{2}{3}})\) 的。此题显然 \(j\) 和 \(dp[i][j]\) 都是整数且不超过 \(n\)，那么就有这个结论。
于是询问的时候只用遍历 \(O(n^{\frac{2}{3}})\) 个点就行了，因此这部分是 \(O(q\times n^{\frac{2}{3}})\)。
题解到这里就结束了，甩了一句 \(O((m+q)n^{\frac{2}{3}})\) 就快进到下一题了。你就不能说说是怎么用 \(O(m\times n^{\frac{2}{3}})\) 把凸包上的点找出来的吗
好好好，等我研究一下别人的代码再说。
好好好，还有一个结论：
- 对一条边 \((u,v)\)，若对于 \(u\) 有一点 \((i,dp[u][j])\) 不在 \(u\) 的凸包上，那么 由 \(dp[u][i]\) 转移而来的 \(dp[v][i]\) 不在 \(v\) 的凸包上。
考虑一个点不在点 \(u\) 的凸包上，由于边都是向后连的，经过黑边相当于所有点整体右移 \(1\) 单位，白边相当于整体上移 \(1\) 单位。
不管怎么动，凸包跟着动，总之不在凸包上的点还是不在凸包上。
又因为 \(dp\) 的转移是取 \(\min\)，那么和 \(v\) 原有的凸包合并以后，这个点不会在凸包上，毕竟左右都有比它优的点。还是画图好理解
这下不用管不在凸包上的点了，直接暴力把所有能到 \(v\) 的 \(u\) 的凸包合并就好。
标签：结论,frac,包上,2023,ICPC,UCup,凸包,dp,times From： https://www.cnblogs.com/jimmywang/p/17233366.html