三角形
描述：
从一堆绳子中找出三根绳子使得围成的三角形的周长最大。
题解：
- 穷举，O($n^3$)
- 先排序，看最大的三根可不可以，不可以，将最大的一根剔除，然后递归。O($n \log_{}n$)
Ants(POJ 1852)
描述：
一堆蚂蚁在一根绳子上，不知道初始朝向，两个蚂蚁相遇会各自掉头，给出每个蚂蚁距离左端的距离和绳子，求出所有蚂蚁掉下绳子的最长时间和最短时间。
题解：
两个蚂蚁相遇掉头就相当于两个蚂蚁穿过对方继续前进。O(n)
Lake Counting(POJ 2386)
描述：
和W相邻的八个square可以认为是连在一起的，构成水洼，计算有多少块水洼。
题解：
用DFS，把和W相邻的变为.,一次DFS解决一块水洼，多少次DFS就有多少块水洼。复杂度：O(8 $\times$ N $\times$ M)
迷宫的最短路径
描述：
寻找迷宫的最短路径
题解：
BFS，用数组记录每一点的距离，不断更新，用队列实现BFS。
硬币问题
描述：
1元、5元、十元、50元、100元的硬币，如何找钱是个数最少。
题解：
贪心算法，但有条件，所有大的硬币的面额都得是小的硬币的倍数。如果上面加入20元的硬币，贪心算法就无法使用
区间调度问题
描述：
有很多工作区间，同时只能干一件事，要求在一段时间内完成最多的工作(个数)
题解：
总是在可选的工作中选取结束时间最早的工作
Best Cow Line(POJ 3617)
描述：
每次可以从S的头部或尾部取一个字符加入到T的尾部，使得最终T的字典序最小
题解：
比较S和反转后S的字典序，取字典序小的那边，贪心。
Saruman’s Army (POJ 3069)
描述：
点覆盖问题，半径R
题解：
贪心
Fence Repair (POJ 3253)
描述：
切木板开销问题
题解：
两个最小板应该是一起切得，贪心。
01背包问题
描述：
背包容量有限，拿或不拿。
题解：
动态规划
最长公共子序列问题
描述：
求两个字符串的最大公共子序列长度，子序列可不连续
题解：
DP
完全背包问题
描述：
每种物品可选任意多件
题解：
改改递推关系式
多重部分和关系
描述：
有n种不同大小的数字$a_i$,每种各$m_i$个。判断是否可以从这些数字之中选出若干使它们的和恰好为K.
题解：
需要记录剩余的数字个数，DP
最长上升子序列问题
描述：
求一个序列的最长上升子序列
题解：
DP，记录以$a_i$结尾的最长上升子序列长度
划分数
描述：
有n个无区别的物品，将它们划分成不超过m组，求出划分方法数模M的余数
题解：
DP，找出状态转移，设dp[i][j]是j的i划分数，有关系dp[i][j]=dp[i][j-i]+dp[i-1][j]
多重集组合数
描述：
n种物品，第i种有$a_i$个，然后一共取m个，有多少种取法
题解：
DP，$dp[i+1][j]=\sum_{k=0}^{min(j,a[i])} dp[i][j-k]$, 可以进一步化简得到: $dp[i+1][j]=dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a_i]$
Expedition (POJ 2431)
描述：
加油问题，要求次数最少
题解：
贪心+优先队列。 不断行驶，当油量为0时，选择经过的最大加油量的加油站。
食物链 (POJ 1182)
描述：
有N只动物，分三类，形成循环状的捕食关系，循环给出两种信息：x和y属于同一类和x吃y，一共K条。其中可能出错，求出出错的消息数。
题解：
用并查集，维护3*N种状态，看是否有矛盾，进行合并操作和查询操作。
二分图判定
描述：
给定一个n个顶点的图，能否最多用两个颜色染色，相邻顶点颜色不同
题解：
用dfs，把相邻的染上不同色，看是否有矛盾
Minimum Scalar Product (GCJ 2008 Round1A A)
描述:
两个向量，内部换序，使得最后的向量积最小。
题解：
设a<b,c<d, 可以证明ad+bc最小。所以只要将两个向量分别排序，最大的和最小的乘就可以。 对于large数据，要用long long
Code:
1 | #include<iostream> |
Crazy Rows (GCJ 2009 Round2 A)
描述:
只交换相邻行，使得主对角线上方的元素都是0，求最小交换次数。
题解：
对于每一行循环，寻找最近的符合条件的，然后交换
Code:
1 | #include<iostream> |