day3下午——dp

正睿青岛

例二 spellcards

SPOJ Twopaths

一定是由一条边分成那个两个联通块，然后分别是里面最长的，求出一个子树内最长的路径，再求出除了这个子树的最长路径。
前缀积，后缀积。

例题：求多少个联通块，包含这个点。

如果带权负数，也求最小的两个。

SPOJ Treecst

枚举删那条边，求直径。

例题：每次询问一个数，将一条边改成这个数，然后查最小直径。
每个边分成的两块的最长直径d1,d2
每个边都有一个函数：
不给，d1 + d2 + x
改：d1 + d2 + c。
取max为直径：根据c的取值，所以开始是一段直线，然后是一段斜率为1的上升的直线，对n个函数求出下凸壳，二分询问。

bzoj 1722

选最多的相邻点对，选的点的和不超过X。
因为点权和开不下，转换状态。
F[x][i]以x为根的子树中，选x ，相邻点的对数为i的最小点权和。
G[x][i]以x为根的子树中，不选x，相邻点的对数为i的最小点权和。
转移：背包。

四边形不等式

相交的->不相交的。

决策单调性，分治（决策单调，不满足单峰，不是一定一个比一个大）
nlogn，每个决策点，在每一层，分到一边。
dp[i][j] = dp[k][j - 1] + w（i, k)

solve(l, r, optl, optr) {
    int mid = (l + r) >> 1;
    for (int i=optl; i<=optr; ++i) 
        dp[mid] ...
    solve(l, mid, optl, optmid);
    solve(mid+1, r, optmid, optr);
}

例5 CF 868 F Minimization-

每次进进入下一层的时候，将所有的optl~mid的数，记录到cnt中。
就是上面代码中，每次进入下一层的时候，记录下cnt。
Codeforces Round #438：F.

柠檬

指定的数字一定是开头结尾，否则可以缩短。