# 笔记：《挑战程序设计竞赛（第2版）》

## Page 16 : 三角形-注脚①

（1）先对n根棍子按长度排序，得到序列L

（2）从L中取最长的三根

• 如果能组成三角形则输出，结束
• 否则删除最长那根，转（2）

## Page 47 : Fence Repair

``````sum( weight(Li) * depth(Li) ) (1 <= i <= n)
``````

## Page 57 : 最长公共子序列问题的注脚①

``````dp[i + 1][j] - dp[i][j] >= 2
``````

``````dp[i][j - 1] - dp[i][j] >= 1        （与定义不符）
``````

``````dp[i][j] - dp[i][j] >= 2            （与定义不符）
``````

``````dp[i + 1][j - 1] - dp[i][j] >= 2
``````

``````dp[i][j - 2] - dp[i][j] >= 1        （与定义不符）
``````

``````dp[i][j - 1] - dp[i][j] >= 2        （与定义不符）
``````

``````dp[i + 1][j - 2] - dp[i][j] >= 2
``````

``````dp[i + 1][0] - dp[i][j] >= 2        （与定义不符）
``````

``````dp[i + 1][j] - dp[i][j] < 2
``````

``````dp[i][j + 1] - dp[i][j] < 2
``````

# Page 113 : 线段上格点的个数

``````a = da * c
b = db * c
``````

# Page 119 : 埃氏筛法

``````// 摘自书中Page 119
int primes[MAX_N];
bool is_prime[MAX_N + 1];

int sieve(int n) {
int p = 0;
for (int i = 0; i < n; i++) is_prime[i] = true;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
prime[p++] = i;
for (int j = 2 * i; j <= n; j += i)
is_prime[j] = false;
}
}
return p;
}
``````