# [USACO17JAN]Balanced Photo平衡的照片

## 题目描述

Farmer John is arranging his NN cows in a line to take a photo (1 \leq N \leq 100,0001≤N≤100,000). The height of the iith cow in sequence is h_ihi, and the heights of all cows are distinct.

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. He decides that cow ii looks “unbalanced” if L_iLi and R_iRi differ by more than factor of 2, where L_iLi and R_iRi are the number of cows taller than ii on her left and right, respectively. That is, ii is unbalanced if the larger of L_iLi and R_iRi is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.

FJ正在安排他的N头奶牛站成一排来拍照。（1<=N<=100,000)序列中的第i头奶牛的高度是h[i]，且序列中所有的奶牛的身高都不同。

## 输入输出格式

The first line of input contains NN. The next NN lines contain h_1 \ldots h_Nh1…hN, each a nonnegative integer at most 1,000,000,000.

Please output a count of the number of cows that are unbalanced.

Code：

# P2014 选课

## 题解

$f(u,k)$

$dp[v][k-1]=dp[u][k]+val$
$dp[u][k]=max(dp[u][k],dp[v][k−1])$

$f(u,k) = max\{f(v,t) + f(u,k-t-1)\}$

# 「一本通 5.1 例 1」石子合并

#### 题目描述

1. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

#### 数据范围与提示

$1≤n≤200。$

Code：

## 题目描述

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

## 输入输出格式

Line 1: Two space-separated integers: N and R

Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Line 1: The length of the second shortest path between node 1 and node N

## 说明

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

## 题解

u的次短路也可以试着更新v的次短路。

Code：

# 二叉苹果树

## 输入输出格式

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

Code：