#
记录写过的dp题目，并分类，尝试总结出某类题目的一般模型.
(题目前打*的未编程验证)
【线性模型】
Tyvj 1049 最长不下降子序列问题 [O(n^2) [还存在基于二分查找的O(nlogn)算法]]
- [状态] f[i]表示从1到i的最长不下降子序列. 最大值需更新.
- [方程] if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)
NOIp 2004 合唱队形 [O(n^2), 双向最长上升子序列]
- [方程] f[i] = max{f[j]}+1 , 枚举k(0<=k<=n).
Rqnoj 164 最长公共子串 [记录方案 子串连续 O(n^2)]
- [状态] f[i][j]表示 子串A第i个字符 和 子串B第j个字符 前 公共子序列长度
- [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j],a[i-1]=b[j-1])|max{f[i-1][j],f[i][j-1]}
UVa 111/10405 [最长公共子序列问题,O(n^2). 可以使用滚动数组降至O(n).]
- [状态] f[i][j]表示 子串A第i个字符 和 子串B第j个字符 前 公共子序列长度
- [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j])|max{f[i-1][j],f[i][j-1]}
UVa 507 [最大连续和,O(n).]
- [状态] f[i]表示当前子序列和(非负)
- [方程] f[i]=max{f[i-1]+a[i], a[i]},递推过程中需更新最大值.
【矩阵模型】
*UVa 10285 滑雪 [记忆化搜索,最长下降子序列二维版本]
- [状态] f[i][j]表示从(i,j)开始的最长下降子序列长度.
- [方程] f[i][j] = max{f[i-1][j], f[i][j-1], f[i+1][j], f[i][j+1]}+1(f[i][j]>f[i-1][j]..)
UVa 108
- 最大矩阵和，O(n^3)，方程不会. 最大连续和的二维版本.
NOIp 2000 方格取数 O(n^4)
- [状态] f[i][j][k][l]表示两人分别到(i,j)、(k,l)所取过的数的和.G[i][j]表示方格里的数.
- [方程] f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
NOIp 2008 传纸条
(1) O(n^4)
- [状态] f[x1][y1][x2][y2] 表示从出发点分别到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示该格的数.
- [方程] f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重复)
- [一个重要优化] 显然有y2=x1+y1-x2(y2>0),因而时间复杂度可以降到O(n^3).Cena显示总用时从近4s降到近0.3s，效果明显.
*(2) O(n^3)
- [状态] f[p][x1][x2],p表示经过的格子数.
- [方程] f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重复)
USACO 5.3.4/3.3.4 [矩阵dp,O(n^2)]
- [状态] f[i][j]表示以(i,j)为右下角的正方形最大边长
- [方程] f[i][j] = min{f[i-1][j], f[i-1][j-1], f[i][j-1]}+1 (0<=i,j<n)
- [预处理] 若G[i][j]=1则f[i][j]=1.
【背包问题】
USACO 3.3.2
- [状态] f[a1][a2][a3][a4][a5]为买a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5时，所需的最少价格
- [方程] f[a1][a2][a3][a4][a5] = min{f[a1-p[i][1][a2-p[i][2][a3-p[i][3][a4-p[i][4]][a5-p[i][5]+p[i][0]} (0<i<=s, ak-p[i][k]>=0,p[i][0]是优惠后的价格)
- [边界条件] f[0][0][0][0][0]=0;
- USACO官方解法很有启发性，用最短路，把每种状态[a1][a2][a3][a4][a5]（a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5）看成一个点，则至多7776个点，而每个优惠就是一条边，则至多105条边。 接下来就是求[0,0,0,0,0]到目标状态的最短路，用Dijkstra(Heap优化)即可.
USACO 3.1.2 [完全背包问题, O(n)或O(n^2).]
- [状态] f[i][j]表示放入第i个物体后剩余体积为j
- [方程] f[i][j] = f[i-1][j] + f[i][j-c[i]]+w[i]
USACO 3.1.6 [完全背包问题,O(n).]
- [状态] f[i]表示凑成i分邮资的最少邮票数.
- [方程] f[i] = min{f[i-v[j]]+1} (i-v[j] >= 0, 0<=i<n, f[0] = 0).
USACO 2.3.4
- [状态] f[i,j]表示前i种货币构成j的方法数，用c[i]记录货币的面值.
- [方程] f[i,j]=f[i-1,j]; 不用第i种货币
f[i,j]=f[i-1,j]+f[i,j-c[i]] 用第i种货币，j>=c[i]
【树形】
USACO 2.3.2
- [状态] f[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则：
- [方程] f[i,j]=∑(f[k,j-1]×f[i-1-k,j-1])(k∈{1..i-2})
- [边界] f[1,i]=1
- 我们要求的是深度恰好为K的方法数S，易知S=f[n,k]-f[n,k-1]。但需要注意的是，如果每次都取模，最后可能会有f[n,k]<f[n,k-1],所以可以用S=(f[n,k]-f[n,k-1]+v) mod v
【其他类型】
USACO 1.5.1 [数字三角形]
- [状态] f[i][j]表示从(i,j)开始经过的数字的最大和
- [方程] f[i][j] = max{f[i+1][j], f[i+1][j+1]}+a[i][j]
USACO 3.3.5 [博弈问题]
- [状态] s[i][j]表示从i加到j的和, 枚举l=j-i. f[i][j]表示从i到j先取者能得到的最大数字和.
- [方程] f[i][j] = s[i][j] - min{f[i+1][j], f[i][j-1]}
USACO 3.2.2
- [状态] f[n][m]表示至多m个1的n位二进制数数量
- [方程] f[n][m] = f[n-1][m] + f[n-1][m-1] (f[0][m] = 1)
数据范围很小，暴力枚举即可.
一开始想复杂了，认为需要枚举出所有符合条件的数字，然后调整顺序，寻找等式 = =
事实上只需要枚举前两个数，然后判断是否符合条件即可.考虑24的情况，若B为1，则还剩下18根火柴.又A<C,所以A为1111.因而只要在[0,1111]内枚举A、B即可.复杂度不会算.
如果范围更大的话，可以令A<=B，枚举A、B.操作数大约是原来的一半.进一步的优化想不到了..
1
#include<stdio.h>
2#include<iostream>
3using namespace std;
4
int num[] = 
{6, 2, 5, 5, 4, 5, 6, 3, 7, 6}, t[2230] = {0};
5int main(){
6
int n, i, j, ans = 0;
7 scanf("%d", &n);
8
for (i = 0; i < 2230; i++){
9 int tmp = i;
10 t[i] += num[tmp%10];
11 while (tmp/10){
12 tmp /= 10;
13 t[i] += num[tmp%10];
14
}
15 }
16 for (i = 0; i < 1112; i++)
17 for (j =0; j < 1112; j++)
18 if (t[i]+t[j]+t[i+j]+4 == n) ans++;
19 printf("%d\n", ans);
20
}
21
http://www.cnblogs.com/dudu/articles/495718.html
详细步骤请看：http://space.cnblogs.com/forum/topic/8550/。
Windows Live Writer配置步骤：
1、在菜单中选择"Weblog";，然后选择"Another Weblog Service"。
2、在Weblog Homepage URL中输入你的Blog主页地址。
3、输入用户名与密码。
4、在“Type of weblog that you are using”中选择“Custom(Metaweblog API)”。
5、“Remote posting URL for your weblog”中输入“http://www.cppblog.com/Blog名/services/metaweblog.aspx”。
使用注意：用Windows Live Writer发布之后，Windows Live Writer并不改变当前窗口的状态(也没有明显的提示)，在当前窗口中会将刚发布的随笔处于编辑状态，如果修改并发布，会直接修改刚发布的随笔内容。
和2000的方格取数如出一辙.数据加强了一点，如果是裸的四维dp可能会超时(80).所以需要优化.
1.普通的四维做法
【状态】f[x1][y1][x2][y2] 表示从出发点分别到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示该格的数.
【方程】f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重复)
【一个重要优化】显然有y2=x1+y1-x2(y2>0),因而时间复杂度可以降到O(n^3).Cena显示总用时从近4s降到近0.3s，效果明显.
2.三维做法(参考官方题解)
【状态】f[p][x1][x2],p表示经过的格子数.
【方程】f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重复)
未编程验证.
3.更优化的做法
dy神牛指出，进一步的优化需要用到最小费用最大流.(NOIP绝对超纲,可以确定不会更深了.)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[52][52][52][52] = {0}, n, G[52][52];
5 int max(int a, int b, int c, int d){
6 if (a < b) a= b;
7 if (a < c) a= c;
8 if (a < d) a= d;
9 return a;
10 }
11 int main(){
12 int m, n, i, j, k, l;
13 scanf("%d%d", &m, &n);
14 for (i = 1; i <= m; i++)
15 for (j = 1; j <= n; j++)
16 scanf("%d", &G[i][j]);
17 for (i = 1; i <= m; i++)
18 for (j = 1; j <= n; j++)
19 for (k = 1; k <= m; k++){
20 if (i+j-k > 0) l = i+j-k; else continue;
21 f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
22 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
23 }
24 printf("%d\n", f[m][n][m][n]);
25 }
26
简单dp，难点在于状态的表示.
题目可以看做两人同时取数，这样就避免了后效性，可以用dp做了.
【状态】f[i][j][k][l]表示两人分别到(i,j)、(k,l)所取过的数的和.G[i][j]表示方格里的数.
【方程】f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
1次WA.
#01: Accepted (75ms, 384KB)
#02: Accepted (0ms, 384KB)
#03: Accepted (0ms, 384KB)
#04: Accepted (28ms, 384KB)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[12][12][12][12] = {0}, n, G[12][12];
5 int max(int a, int b, int c, int d){
6 if (a < b) a= b;
7 if (a < c) a= c;
8 if (a < d) a= d;
9 return a;
10 }
11 int main(){
12 int a, b, c, i, j, k, l;
13 scanf("%d", &n);
14 for(;;){
15 scanf("%d%d%d", &a, &b, &c);
16 if (a || b || c) G[a][b] = c;
17 else break;
18 }
19 for (i = 1; i <= n; i++)
20 for (j = 1; j <= n; j++)
21 for (k = 1; k <= n; k++)
22 for (l = 1; l <= n; l++){
23 f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
24 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
25 }
26 printf("%d\n", f[n][n][n][n]);
27 }
28
[地址]http://hi.baidu.com/yali79/blog/item/3d231901230291007aec2c71.html
21世纪NOIP提高组复赛考察点详细分析
By hpfdf @YALI
引用资料:
NOIP2000~2009原题。
| 题目编号 | 题目名 | 主考察点 | 知识点 | 系数 |
| NOIP-2000-A | 进制转换 | 数学 | 初等代数,找规律 | 0.6 |
| NOIP-2000-B | 乘积最大 | 动态规划 | 资源分配DP | 0.7 |
| NOIP-2000-C | 单词接龙 | 搜索 | DFS,字符串,模拟 | 0.5 |
| NOIP-2000-D | 方格取数 | 动态规划 | 多维状态 | 0.6 |
| NOIP-2001-A | 一元三次方程求解 | 数学 | 数学,枚举,实数处理 | 0.5 |
| NOIP-2001-B | 数的划分 | 动态规划 | 资源分配DP,多维状态DP | 0.7 |
| NOIP-2001-C | 统计单词个数 | 动态规划 | 资源分配DP,字符串 | 0.3 |
| NOIP-2001-D | Car的旅行路线 | 图论 | 最短路,实数处理 | 0.7 |
| NOIP-2002-A | 均分纸牌 | 贪心 | 贪心,模拟 | 0.8 |
| NOIP-2002-B | 字串变换 | 搜索 | BFS,字符串 | 0.5 |
| NOIP-2002-C | 自由落体 | 数学 | 数学,物理,模拟,实数处理 | 0.6 |
| NOIP-2002-D | 矩形覆盖 | 构造 | 动态规划/贪心/搜索剪枝 | 0.2 |
| NOIP-2003-A | 神经网络 | 图论 | 拓扑排序,第推 | 0.4 |
| NOIP-2003-B | 侦探推理 | 模拟 | 枚举,模拟,字符串 | 0.5 |
| NOIP-2003-C | 加分二叉树 | 动态规划 | 树,区间DP | 0.4 |
| NOIP-2003-D | 传染病控制 | 构造 | 随机贪心/搜索剪枝 | 0.2 |
| NOIP-2004-A | 津津的储蓄计划 | 模拟 | 模拟 | 0.9 |
| NOIP-2004-B | 合并果子 | 贪心 | 最优哈夫曼树,排序 | 0.7 |
| NOIP-2004-C | 合唱队形 | 动态规划 | 子序列DP | 0.7 |
| NOIP-2004-D | 虫食算 | 搜索 | 搜索剪枝,模拟 | 0.2 |
| NOIP-2005-A | 谁拿了最多奖学金 | 模拟 | 模拟,字符串 | 0.8 |
| NOIP-2005-B | 过河 | 动态规划 | 子序列DP,贪心优化 | 0.2 |
| NOIP-2005-C | 篝火晚会 | 数学 | 置换群,贪心 | 0.2 |
| NOIP-2005-D | 等价表达式 | 模拟 | 字符串,抽样检测,表达式 | 0.3 |
| NOIP-2006-A | 能量项链 | 动态规划 | 区间环DP | 0.6 |
| NOIP-2006-B | 金明的预算方案 | 动态规划 | 资源分配DP,构造 | 0.6 |
| NOIP-2006-C | 作业调度方案 | 模拟 | 模拟 | 0.7 |
| NOIP-2006-D | 2^k进制数 | 动态规划 | 动态规划/组合数学,高精度 | 0.5 |
| NOIP-2007-A | 统计数字 | 模拟 | 排序 | 1.0 |
| NOIP-2007-B | 字符串的展开 | 模拟 | 字符串,模拟 | 0.7 |
| NOIP-2007-C | 矩阵取数游戏 | 动态规划 | 区间DP,高精度 | 0.6 |
| NOIP-2007-D | 树网的核 | 图论 | 最短路,树的直径 | 0.4 |
| NOIP-2008-A | 笨小猴 | 模拟 | 质数判断,字符串 | 1.0 |
| NOIP-2008-B | 火柴棒等式 | 模拟 | 枚举,优化/开表 | 0.8 |
| NOIP-2008-C | 传纸条 | 动态规划 | 多维状态DP | 0.7 |
| NOIP-2008-D | 双栈排序 | 构造 | 枚举,贪心/二分图 | 0.4 |
| NOIP-2009-A | 潜伏者 | 模拟 | 字符串,模拟 | 0.9 |
| NOIP-2009-B | Hankson的趣味题 | 数学 | 初等数论,质因数,组合数学 | 0.4 |
| NOIP-2009-C | 最优贸易 | 图论 | 最短路 | 0.5 |
| NOIP-2009-D | 靶形数独 | 搜索 | 搜索优化 | 0.3 |
动态规划：12
模拟：10
数学：5
图论：4
搜索：4
构造：3
贪心：2
【动态规划】平均难度系数：0.55
次项为历届NOIP考察次数最多的知识点。
主要有 1.区间模型 2.子序列模型 3.资源分配模型 以及一些简单的多维状态设计技巧。
动态规划可以与图,树,高精度等知识点配合出题。
【模拟】平均难度系数：0.76
平均每届NOIP都会出现1个模拟题。
这种题一般算法很简单，需要选手细心理解题目意思，注意细节。考察选手的代码实现能力。
【数学】平均难度系数：0.46
需要掌握质数及其性质，基础的实属操作，加法原理和乘法原理。此类题需要选手对数学规律的灵感。
【图论】平均难度系数：0.50
历届考察点基本上都是1.最短路问题 和 2.特殊图的性质 。特殊图包括树，拓扑图，二分图等。
历届NOIP在图论上的考察并不是很多。
【搜索】平均难度系数：0.38
历届搜索题一般都比较难，搜索算法本身简单，于是题目会提高选手对其他方面的要求。
主要有搜索优化和模拟。写搜索题时应该以尽量多得分为目标。
【构造】平均难度系数：0.27
构造类题目一般没有明确的算法，需要选手仔细分析题目的实质，并得出解法。
这个解法通常不是唯一的。有时一个好的贪心可以得相当多的分。有时搜索剪枝可以很大的提高效率。
同样以多得分为目标。
【贪心】平均难度系数：0.75
此类题需要选手对算法的直觉，贪心正确性一旦被证明，通常题目就很简单了。
(×)友情提醒：
考场上没有标示每道题属于什么类型，光分析历届类型是没用的。
想要得高分，还得多做题。
http://www.cnblogs.com/TerryFeng/archive/2009/01/30/1381483.html
由于cppblog和cnblogs使用的系统相同，因而可以使用Windows Live Writer直接编辑.
拓扑排序
虽然AC了，但还是觉得自己很不在状态.
1#include<stdio.h>
2#include<string.h>
3bool G[110][110];
4int in[110], m, n;
5struct stack{
6 int q[110], t;
7 stack() {memset(q, 0, sizeof(q)); t= 0;}
8 void push(int x) {q[++t] = x;}
9 int pop() {return q[t--];}
10 bool empty() {return t ? 0 : 1;}
11};
12void toposort(){
13 stack s;
14 int p[110], t = 0, i, j;
15 bool flag[110] = {0};
16 for (;;){
17 if (t == m) break;
18 for (i = 1; i <= m; i++)
19 if (!in[i] && !flag[i]) s.push(i);
20 while (!s.empty()){
21 i = s.pop();
22 p[++t] = i;
23 flag[i] = 1;
24 for (j = 1; j <= m; j++)
25 if (G[i][j]) in[j]--;
26 }
27 }
28 for (i = 1; i < t; i++)
29 printf("%d ", p[i]);
30 printf("%d\n", p[t]);
31}
32int main(){
33 int i, x, y;
34 while (scanf("%d%d", &m, &n) == 2 && (m || n)){
35 memset(G, 0, sizeof(G));
36 memset(in, 0, sizeof(in));
37 for (i = 1; i <= n; i++){
38 scanf("%d%d", &x, &y);
39 G[x][y] = 1;
40 in[y]++;
41 }
42 toposort();
43 }
44}
45
由于求导在函数方面出人意料的应用，所以被迫开始复习求导. = =
1.单调性
在某一区间内f '(x)>0 => 在此区间内函数单调递增
在某一区间内f '(x)<0 => 在此区间内函数单调递减
2.极值
当x=a时取极值，则有f '(a)=0
3.凹凸性
f ''(x)>0 下凸曲线
f ''(x)<0 上凸曲线
貌似就这些了，不过答题格式还是一个问题...这次数学作业就当实验算了 = =
引：“我们要把厚书读薄，再把薄书读厚.”
进一步的系统化将在读完这本书后，以表格或者思维导图的形式出现.
一、乘法原理
乘法原理讨论分阶段办事过程中的计数问题.
用集合论观点解释：
把分阶段进行的事情看作一种多重选取过程，每一个过程都是自某个集合挑选一个元素，然后考虑有多少种不同的挑选方式.
【应用】数的整除，因数分解问题
【例3】2160的正约数个数.
2160 = 2^4 * 3^3 * 5^1
则任意约数形式为2^i * 3^j * 5 ^k (0<=i<=4, 0<=j<=3, 0<=k<=1)
所以约束个数为(4+1)(3+1)(1+1)=32.
【例5】从题目中抽象出模型.
【例6】 一个结论：[u,v]=n, 令n的因子r的个数为n(r)，有k个因子.
则符合要求的数对个数为 (2n(r)+1)*..*(2n(r)+1).
需要注意的是最大公约数，是去两数某因子的最大值.
【例7】补集思想.(排除法)
在整除性问题中，确定前n-1位，然后分类讨论第n位的情况.
【例8】看了，未懂.
二、重复排列
【定义】如果在同一个n阶集合(有n个元素)中依次进行k次选取，而且选过的元素还可以再选，则一共有n^k中不同的选取方式(即重复排列方式).
【应用】空间解析几何、集合子集性质的讨论
【例5】立方体{(x,y,z):0<=x,y,z<=a}顶点坐标.
证 显然每个顶点(x,y,z)的三个坐标都是集合{0,a}的元素，所以共有2^3个不同的顶点.坐标略.
【例6】在三维欧氏空间给出9个格点(坐标值为整数)，求证其中必有两点中点坐标为格点.
证 若两点A(x1,y1,z1)和B(x2,y2,z2)的中点为格点，必有x1和x2，y1和y2，z1和z2和为偶数，即两者奇偶性相同.
考虑考虑欧氏空间格点奇偶性情况可知，每个坐标值都是{奇数，偶数}中一个元素，所以格点有8种不同的奇偶性.从而，原命题由抽屉原理可证.
【例7】n阶集合共有2^n个子集，2^n-1个真子集.
【例9】棋盘问题，从左下角走到右上角，n+1行，m+1列，求证f(m,n)<=2^(mn).
证 道路将城市分成mn个方块，而路线又将方块分成两个子集(其中一个可能为空)，显然不同子集个数为2^(mn).即f(m,n)<=2^(mn)，当且仅当m=n=1时等号成立.
三、排列
【定义】从n个不同的元素中有次序地选取k(1<=k<=n)个，叫做从n个不同元素中取出k个元素的一个排列.
【应用】组数问题中的“无重复数字”问题.
【例4】利用补集思想处理无重复数字问题.考虑不参加组数的数字整除情况和所有数字整除情况(联系1.7)
【例5】逐位讨论.
【例7】注意到k个数字取自不同行列(联想皇后问题)，所以子集个数为k!，每个子集的和分行列讨论，累加即可.
【例10】有2n个人参加收发电报培训，每两人结为一对互发互收，有多少种不同的结对方式.(搭配问题)
解 (2n-1)(2n-3)...3*1=(2n)!/(2^n*n!)
需要注意的是求和使用的思想: 先求出全部数的积，然后去掉里面的偶数.也是一种间接的方法.
四、加法原理
【集合的分划】
若把一个集合B分成一些子集B1,B2,...,Bk，使得
(i)B1∪B2∪...∪Bk = B;
(ii)B1∩B2=∅ ,...，Bk-1∩Bk=∅.满足这两条性质的子集B1,B2,...,Bk，叫做B的一个分划.
【定义】
|B|=|B1|+|B2|+...+|Bk| 加法公式
这种通过分划计数的原理叫做加法原理.
【例1】现有长度分别为1,2,...,n的细木棍各一根，可以以它们为边构成多少种不同的三角形?
解 以c的长度对这些三角形分类，将c=k的三角形集合记做Bk，则构成了集合B的一个分划.
在Bk中，三角形三边分别为a<b<k，其中k为定值，于是可将
(a,b)对应于平面中的格点.通过限制条件a<k,b<k,a+b>k我们可以知道，符合条件的格点在a=b,a+b=k,b=k三条直线围成的三角形内,
所以若k为偶数，有|Bk|=1/4*(k-2)^2
若k为奇数，有|Bk|=1/4(k-1)(k-3)
从而可以求得|B|.(二阶等差数列求和不熟)
【例2】求方程x^2-[x]^2=(x-x[x])^2在区间[1,n]中根的数目.
解
将区间[k,k+1)中根的集合记做Bk.若x∈[k,k+1)，记k=[x],p=x-[x](0<=p<1)，可得2kp=[2kp+p^2].
显然等式两边为整数，所以p=0,1/2k,...,2k-1/2k，故而|Bk|=2k。
由加法原理可知，|B|=n^2-n+1
五、带限制条件的排列问题
(i) 间接方法
【排除法】先假定不存在限制条件，求出所有情况的数目；再考虑受到限制条件，而不允许出现的情况数目.
(ii) 直接方法
【优限法】优先解决受限对象(受限对象或受限元素)的安置，然后再考虑一般对象的安置问题.
【插入法】首先安排一般元素，然后将首先元素插入到允许的位置上.(某些元素相邻或者不相邻)
【视一法】首先要把要求相邻排列的元素看成一个整体，同其他元素一同排列，然后再考虑这个整体内部的元素间的排列问题.
【例8】10个节目中有6个演唱，4个舞蹈，要求每两个舞蹈之间至少安排一个演唱.
解 反过来看问题，原命题等价于在任意两演唱(边界情况的话一个)中安排或不安排一个舞蹈，而这样的可能位置共7个.所以共6!*P(7,4)种顺序.
六、组合
【定义】从n个不同物件中无次序地(不计顺序地)选取k个，叫做从n个物件中选k个的一个组合.
如果考虑k个物件的选取顺序，可得P(n,k)=C(n,k)*k!
从而得到组合的计算公式C(n,k)=n!/k!(n-k)!
(i)C(n,n-k)=C(n,k)
(ii)C(n,k)+C(n,k-1)=C(n+1,k)