有东西被加密了, 请输入密码查看.

朴素的状态为 设 \(f_{i,j}\) 为前 \(i\) 束花，放在前 \(j\) 个花瓶的最大收益。 由题意得，如果把花的编号看作数值，它所在的花瓶编号为下标，那么是不允许逆序对的存在的。编号为 \(i\) 的花必须放在 \(i+1\) 的左边。 也就是说，对于一个 \((i,j)\)，前 \(i-1\) 束花只能在 \([1,j-1]\) 这个区间内放置，与后面怎么放无关，「无后

有东西被加密了, 请输入密码查看.

分析 设 \(d(x)\) 为 \(1\) 到 \(x\) 的最短路径长度，\(cnt(x)\) 为最短路条数。 不难发现，对于一条特殊边 \((1 \rightarrow x)\)，边权为 \(w\)，它能被删除，当且仅当满足以下条件之一。 \(w > d(x)\) \(w= d(x)\) 并且 \(cnt(x) > 1\) 所以直接在图上跑 Dijkstra，求

有东西被加密了, 请输入密码查看.

分析 根据小学学的乘法分配律，并且手算一下，能够发现，如果要把整个序列分成若干段，那么不同的分割顺序不会对最终得分产生影响。 比如样例的方法是1 3 5，如果我们按照5 3 1来分，答案也是一样的。 然后划分方法就没有后效性了，我们可以定义一个固定的划分顺序。按照习惯都是从左往右去分。 设 \(f_{i,k+1}\) 为前 \(i\) 个数字，划分成 \(k+1\) 段的最大得分。状态看

有东西被加密了, 请输入密码查看.

有东西被加密了, 请输入密码查看.

有东西被加密了, 请输入密码查看.

分析 有一个显然的结论：设当前已经获得的名字个数为 \(k\)，那么再获得其他名字的概率为 \(\frac{n-k}{n}\)。也就是说，平均买 \(n\) 次有 \(n-k\) 个其他的名字，那么再获得一个平均次数为 \(\frac{n}{n-k}\)。 感性理解一下。 事实上有这个定理，对于事件 \(A\)，有 \(P(A)=p\)，那么发生 \(A\) 的期望次数 \(E(A)=