测试页

测试

年轻人的第一个博客！

---

fluid 折叠测试：

文字 或者 markdown 均可

---

Details 折叠测试：

点击展开

这是一个折叠的内容

My Details自定义折叠细节组件

这是一个折叠的内容

do something

Example例题

斜率优化模板题

Print Article HDU3507

\(\texttt{Description}\)

打印一篇有 \(N\) 个字的文章，每个字i的打印成本是 \(C_i\)。

此外，在一行中打印 \(k\) 个字将花费: \((\sum\limits_{i=1}^{k} C_i)^2 + M\)。

\(M\) 是一个常数。你的任务是找到一种最佳的打印方式，使得总的打印成本最小。

\(\texttt{Input}\)

有很多测试用例。

对于每个测试用例，第一行有两个数字\(N\)和\(M\)（0 ≤ n ≤ 500000，0 ≤ M ≤ 1000）。

然后，下面的第\(2\)到第\(N + 1\)行有N个数字。输入以\(EOF\)结束。

\(\texttt{Output}\)

对于每个测试用例，输出一个整数，表示最小的打印成本。

题解

设 \(dp[i]\) 为前 \(i\) 个单词的最低成本，\(sum[i]\) 为前缀和。

\[ \begin{align*} \because dp[i] &= \min(dp[j] + (sum[i] - sum[j])^2 + M) \\ &= \min(dp[j] + sum[i]^2 - 2 \times sum[i] \times sum[j] + sum[j]^2 + M) \\ \therefore(dp[i] - sum[i]^2) &= \min(dp[j] + sum[j]^2 - 2 \times sum[i] \times sum[j]) + M \\ &= (dp[j] + sum[j]^2) - (2 \times sum[i] \times sum[j]) + M \\ \therefore(dp[j] + sum[j]^2) &= (2 \times sum[i] \times sum[j]) + (dp[i] - sum[i]^2) - M \\ \end{align*} \]

\[ 设~ y = dp[j] + sum[j]^2,~ x = sum[j],~ k = 2 \times sum[i],~ b = dp[i] - sum[i]^2 - m,~则有： \]

\[ y=kx+b \]

\(x=sum[j]\) 和 \(k=2\times sum[i]\) 都是单调不减，满足斜率优化的要求。

#include <bits/stdc++.h>
using namespace std;
const int N = 500007;
int n, m, c[N], sum[N], dp[N];  // dp[i] 表示前 i 个字的最小打印成本
int q[N], head, tail;
#define K(p) (2 * sum[i])
#define X(p) (sum[p])
#define Y(p) (dp[p] + sum[p] * sum[p])
#define B(p) (dp[i] - sum[i] * sum[i] - m)
// le -> less or equal (<=) , ge -> greater or equal (>=)
// lt -> less than (<) , gt -> greater than (>)
// 以下两行可以避免除法（除法会有误差和除数为0的情况）
// 一定要注意p1和p2的顺序，p1在p2的右边，即p1的x坐标大于p2的x坐标，否则斜率算的是反的
#define slope_le_k(p1, p2 ,k) ((Y(p1) - Y(p2)) <= (X(p1) - X(p2)) * (k))
#define k1_le_k2(p1, p2, p3, p4) ((Y(p1) - Y(p2)) * (X(p3) - X(p4)) <= (Y(p3) - Y(p4)) * (X(p1) - X(p2)))
int main() {
    while (cin >> n >> m) {
        dp[0] = 0;
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
            sum[i] = sum[i - 1] + c[i];
        }
        head = 1, tail = 1; // 初始化单调队列: 放入一个元素0 (也抛弃了q[0]，选择下标从1开始)
        q[tail] = 0;        // 这里是 j == 0的情况，只有一个点，所以不需要判断斜率直接放入
        for (int i = 1; i <= n; i++) {
            // 这里不能是 head <= tail ！！！因为至少要有两个元素才能计算斜率
            // 并且也可能是特殊情况：当所有线段的斜率都 <= k 时，此时队列必须剩下一个元素
            // 注意q[head + 1], q[head]的顺序，确保斜率不要反了！！！
            while (head < tail && slope_le_k(q[head + 1], q[head], K(i))) head++;   
            int j = q[head];    // 队首的 j 是最优决策点
            dp[i] = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;  // 计算 dp[i]
            // 下一轮的点(x_j,y_j)(j = i)加入图中，并更新凸壳（因为j < i，所以这里是下一轮）
            // 由于队列中的点都是凸包上的点，所以这里只需要判断队尾的点是否在凸包外即可
            while (head < tail && k1_le_k2(q[tail], i, q[tail - 1], q[tail])) tail--;
            q[++tail] = i;
        }
        cout << dp[n] << endl;
    }
    return 0;
}

绘图测试：

xxxxxxxxxx60 1<% if(theme.post.math.engine === 'mathjax') { %>2 <%3    var lazy = theme.lazyload.enable && require_version(theme.static_prefix.mathjax, '3.2.0')4​5    import_script(6      <script>7        if (!window.MathJax) {8          window.MathJax = {9            tex   : {10              inlineMath: { '[+]': [['$', '$']] }11            },12            loader : {13              ${ lazy ? 'load: \[\'ui/lazy\'\]' : '' }14            },15            options: {16              renderActions: {17                insertedScript: [200, () => {18                  document.querySelectorAll('mjx-container').forEach(node => {19                    let target = node.parentNode;20                    if (target.nodeName.toLowerCase() === 'li') {21                      target.parentNode.classList.add('has-jax');22                    }23                  });24                }, '', false]25              },26              lazyAlwaysTypeset: (function() {27                // 检查页面上是否存在 'mydetails' 元素28                if (!document.querySelector('mydetails')) {29                  return null; // 如果不存在，返回 null30                } else {31                  return ['mydetails']; // 如果存在，返回包含 'mydetails' 的数组32                }33                // 如果你直接给一个列表，那么如果页面上不存在这个元素，MathJax 将会崩溃34              })(),35            }36          };37        } else {38          MathJax.startup.document.state(0);39          MathJax.texReset();40          MathJax.typeset();41          MathJax.typesetPromise();42        }43​44        Fluid.events.registerRefreshCallback(function() {45          if ('MathJax' in window && MathJax.startup.document && typeof MathJax.startup.document.state === 'function') {46            MathJax.startup.document.state(0);47            MathJax.texReset();48            MathJax.typeset();49            MathJax.typesetPromise();50          }51        });52      </script>53    )54​55    import_js(theme.static_prefix.mathjax.replace('es5/', ''), 'es5/tex-mml-chtml.js')56 %>57​58<% } else if (theme.post.math.engine === 'katex') { %>59 <% import_css(theme.static_prefix.katex, 'katex.min.css') %>60<% } %>ejs

---

嵌入 Draw.io SVG 浏览器测试：

会导致 MathJax 崩溃，暂时不使用。。

---

MathJax 测试

\[ \begin{align} \frac{1}{2} + \frac{1}{3} &= \frac{5}{6} \\ \frac{1}{2} + \frac{1}{3} &= \frac{5}{6} \\ \end{align} \]

\[ The\ quick\ brown\ fox\ jumps\ over\ the\ lazy\ dog. \]