「JSOI2011」汇总

标签：long   main   splay   rod   math   lld   参考   传送门   ace   

「JSOI2011」柠檬

斜率优化题。
在优化前，还有一个值得一提的优化：
对于最后的最有分割方案，每一段的两个端点一定是同颜色的，并且作为这一段的 \(s_0\)
证明：如果不作为这一段的 \(s_0\)，那么它显然没有贡献，把这一个单独分出来显然更优，直到最后两个端点就一定都是 \(s_0\) ，颜色相同。
那么我们只需要从之前和该点种类相同的位置进行转移即可。
这样就从直接枚举的复杂度 \(O(n^3)\) 优化到了 \(O(n^2)\) ，但还是不够，继续考虑优化。
我们先把转移方程写出来：
\(dp_i\) 表示把前 \(i\) 个取完，且 \(i\) 点作为一段的终点最大收益。
\[dp_i=\max\limits_{1\le j \le i,a_j=a_i}\left\{dp_{j-1}+s_i(p_i-p_j+1)^2\right\}\]
\(p_i\) 表示第 \(i\) 个点是种类为 \(s_i\) 的第 \(p_i\) 个点。
根据斜率优化的一些做法，我们可以把式子化成这样：
\(p_i\times 2p_js_j+dp_i-s_i(p_i+1)^2=dp_{j-1}-2a_jp_j+a_jp_j^2\)
设 \(x_i = 2s_ip_i,y_i=dp_{i-1}-2s_ip_i+s_ip_i^2\)
\(p_ix_j+dp_i-s_i(p_i+1)^2=y_j\)
因为要让 \(dp_i\) 最大化，所以我们对每一种颜色都用单调栈维护一个上凸包，这样才能满足决策单调性。
注意一点细节：
因为我们的转移点 \(j\) 的范围是 \([1,i]\) 的，而我们再插入 \(j\) 这个点时只有 \(dp_{j-1}\) 这个信息，为了能取到 \(dp_{i-1}\) ，我们需要在寻找最优转移点之前就把 \(i\) 加入单调栈。
参考代码：

#include 
#include 
#define rg register
#define int long long
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0'  stk[_];

inline int X(int i) { return 2 * s[i] * p[i]; }

inline int Y(int i) { return dp[i - 1] - 2 * s[i] * p[i] + s[i] * p[i] * p[i]; }

inline double slope(int i, int j) { return (double) (Y(i) - Y(j)) / (X(i) - X(j)); }

signed main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(n);
    for (rg int i = 1; i  1 && slope(A, B)  1 && slope(A, B) 

「JSOI2011」分特产

传送门
计数题。
考虑容斥掉每人至少一个的限制。
就直接枚举至少有多少人没有分到特产，然后剩下的随便分。
\[Ans = \sum_{i = 0}^n (-1)^i {n \choose i} \prod_{j = 1}^m {n - i + a_j - 1 \choose n - i - 1}\]
参考代码：

#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' 

「JSOI2011」汇总

标签：long   main   splay   rod   math   lld   参考   传送门   ace   

原文地址：https://www.cnblogs.com/zsbzsb/p/12244376.html