道阻且长

题意：在一条高速公路边上有 V 个村庄，用一条坐标轴来描述这条公路，每个村庄的坐标各不相同，且都是整数。两个村庄间的距离用他们的坐标值差的绝对值表示。现在要在这些村庄中选出 P 个建立邮局，邮局建立在村庄里，每个村庄使用离他最近的那个邮局。求一种建设方案，使得所有村庄到各自所使用的邮局的距离总和最小。

思路：动态规划
考虑 i 个邮局控制 j 个村庄的情况，假定已知 i -1 个邮局控制了 j 中的 k 个村庄，由此递推第 i 个邮局控制从 k 到 j 的村庄所获得的最小值就是 i 个邮局控制 j 个村庄的最优值。

cost[i][j] = min(cost[i - 1][k]) + newcost[k + 1][j] (1 < = i <= j <= n && i - 1 <= k < j)
cost[i][j] 表示前 i 个邮局控制前 j 个村庄的距离最小值。
newcost[k + 1][j]表示第 i 个邮局控制第 k + 1 村庄到第 j 个村庄时的距离最小值，这个最小值就是第i个邮局建在(k + 1 + j) >> 1个村庄。
Read the rest of this entry »

题意：问价值 1 到 6 的个数分别为num[i]（1 < = i <= 6） 问其总价值能否被平分。
思路：动态规划

强烈推荐这个题目，有几种做法，一种是直接的 DP，由于范围过大，可能超时。数学上的分析可以极大减小范围，倍增思想也可以一定程度上减少区间。
时间复杂度：0 - 1背包，复杂度O（n * s) (n ＝ num[i]的和, s = sum / 2(sum 总价值))
首先由于 num[i] 很大，用朴素的背包方法人会超时，故要进行一些预处理，不难发现 num[i] = 1 + (1 << 1) + (1 << 2) + (1 << k) + res(余数) (1 << (k + 1) > num[i]) ，这样从 1 到 num[i] 的数都可由2 ^ i （0 < = i <= k)和 res(余数）组成。

Read the rest of this entry »

题意：整数划分。
思路：在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n, m).可以建立q(n, m)的如下递归关系。
（1） q(n, 1) = 1, n >= 1.

当最大加数不大于1时，任何正整数n只有一种划分形式，即n = 1 + 1 + …… + 1.(n 个1）
（2） q(n, m) = q(n, n),m >= n

最大加数n1实际上不能大于n。因此，q(1, m) = 1.
(3) q(n, n) = 1 + q(n, n - 1).

正整数n的划分由n1 = n的划分和n1 < = n - 1的划分组成。
（4）q(n, m) = q(n, m - 1) + q(n - m, m), n > m > 1.

正整数 n 的最大加数 n1 不大于 m 的划分由 n1 = m 的划分和 n1 < = m - 1 的划分组成。
Read the rest of this entry »

跳板游戏。
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy 老鼠在时刻 0 从高于所有平台的某处开始下落，它的下落速度始终为 1 米/秒。当 Jimmy 落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是 1 米/秒。当 Jimmy 跑到平台的边缘时，开始继续下落。Jimmy 每次下落的高度不能超过 MAX 米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到底地面时可能的最早时间。
从上往下，递推，每次不是向左就是向右。
Read the rest of this entry »

题意：容器中有 n 种原子，现提供 m 种光子，这 n 种原子中能量之差等于提供的 m 种光子之一所具有的能量，就认为这两种原子是处在容器在是危险的，现在要求取走一些原子，使得容器中的原子处在一块是安全的，同时要求剩下的原子的能量和最大。
感觉和翻骨牌的那道题目很类似。
Read the rest of this entry »

这个题目也是线段树的典型题。
有一系列村庄，然后对一些村庄进行破坏或修复。让你求与某村庄直接或间接相连且都没有破坏的村庄数量。
对于每一个区间，用线段树维护从区间左端点开始的最大连续没破坏的村庄数量 Lx 以及以区间右端点结点的最大连续没破坏的村庄数 Rx，很容易更新这两个值及求出要求的数量。
线段树就是这样，在节点除了自身的编号，其它的含义由你自己去添加，在每次修改时呈树状更新，查询时更快了。
Read the rest of this entry »

说三辆汽车要投递杂志到 N 个地方：L1，L2，，，LN，在最初，3 辆车都停留在原点，只有在 Li-1 被投递之后 Li 才能被投递，任何时候只能有 1 辆汽车是活动的，给定汽车从 Li 到 Lj 所需要的时间，求完成投递所需要的最短时间。
假设 dp[i][j][k] 表示当 3 辆车位于 i，j，k 时完成全部投递所需要的时间。
假定 i< =k，j<=k。
dp[i][j][k] = min(dp[i][j][k + 1] + t[k][k + 1], dp[j][k][k + 1] + t[i][k + 1], dp[i][k][k + 1] + t[j][k + 1])。
Read the rest of this entry »

天平有若干砝码，给定挂钩的数量和位置，问有多少种使天平挂平衡的方法。
用二维数组 dp[x][y+7500] 记录挂 x 个砝码时力矩为 y 时的方法数，将砝码一一挂上，最后记录所有砝码都挂上时的 dp[x][7500] 的值。
为什么要加上 7500？因为力矩可能是负值。
Read the rest of this entry »

这是一个所谓的多重背包问题。有 N 套邮票，每套有几种的面值，问可以组成的连续总面值最大是多少。
例如，输入：
5
2
4 1 4 12 21
4 1 5 12 28
意思是最多允许 5 枚邮票，第一套共 4 种，面值分别是 1 4 12 21，第二套面值是 1 5 12 28。则 1 4 12 21 这一套可以达到的最大连续的总面值是 71。
其实也是个组合数学母函数问题。
Read the rest of this entry »

罗嗦了半天，其实就是求最长的不递减序列。
基本的动态规划问题，转移方程：D[i] = max{1, D[j] + 1} (j = 1, 2, 3, ..., i-1 且 A[i] < A[j])。
Read the rest of this entry »

将由 A 到 Z 的 26 个字母分别表示为 1 到 26 的数字，问给定一个数字串，它被还原为字符串时有多少种情况。比如 25114 还原为字符串结果为 'BEAN', 'BEAAD', 'YAAD', 'YAN', 'YKD' and 'BEKD'，共 6 种情况。
Read the rest of this entry »

有 N 只奶牛，每只奶牛有几个首选活动范围，表示为几个坐标点，现在需要用一根绳子将所有奶牛拴在一起构成一个封闭多边形，求多边形最小长度，注意每个奶牛都要位于一个它首选的活动点上。
设 len[c][i][j] 表示第 0 只奶牛的第 c 个点到第 i 只奶牛的第 j 个点的最短距离，D[(i, j), (k, l)] 表示第 i 只奶牛的第 j 个点和第 k 个奶牛的第 l 个点之间的距离。cnt[i] 表示第 i 只奶牛的活动点数目。
则 len[c][i][j] = min{len[c][i-1][k] + D[(i-1, k), (i, j)]}，其中 0 < = k <= cnt[i]。
Read the rest of this entry »

一个矩阵，每个元素代表一个费用，要求找到一条从矩阵第 1 行到最后一行的最小费用路径（不同行之间只能从上往下一行的同一列走，同行可以向左或向右走）。
强烈推荐此类题目。需要熟练掌握。
Read the rest of this entry »

一共有 2 棵苹果树，一头奶牛站在其中一棵苹果树下等待苹果落下，由于任意一个时刻只能站在一棵树下，所以当苹果从另外一棵树上掉下来时，它不得不移动到另外的一棵树下去抓苹果，假定任意一分钟只有一棵树上掉下苹果，它只要站在正在掉苹果的树下就一定能抓住这个苹果，它从一棵树移动到另外一棵树的时间不计，奶牛不愿意太频繁移动，现在给定苹果的下落次序和最大移动次数，问奶牛最多可以抓住几个苹果。
动态规划。dp[i][j] 表示往返 i 次并且在树 j 的状态下抓到的最多苹果数目。
Read the rest of this entry »

题目描述：
给你m个东西，放在n个相同的盒子中（相同，即不计顺序），每个盒子可以放任意多，问有多少种放法。
这是组合数学母函数的典型应用。
Read the rest of this entry »