HDU2955 - Robberies
Robberies 依然是01背包，但这次的有点特殊。特殊之处在于，背包的总体积是可以获得的钱的最大值( 如果是以概率为背包也不能枚举啊23333 )，然后用动态规划求得获得该钱数被抓的最大概率( 如果在最大概率的情况下都不会被抓，那就肯定不会被抓 )。
Read moreHDU2639 - Bone Collector II
Bone Collector II 这道题与Bone Collector的不同之处在于，这道题求的是第k优解，而非最优解。那应该怎么做呢？ 首先，01背包的核心方程式dp[j] = max(dp[j] , dp[j - w[i]] + v[i]) ,也就是说，每一个新状态都是由dp[j]或dp[j - w[i]] + v[i]转移来的。我们首先用一个数组a[]和一个数组b[]将这两个状态存起来，然后再循环求得第k优解。这个过程有点像是，一个年级有两个班，我需要知道全年级的前十名是谁，那我就可以通过得到第一个班的前十是谁和第二个班的前十是谁来求得全年级的前十。 代码如下： #include <iostream> #include <cstdio> #include <cs..
Read moreHDU2602 - Bone Collector
Bone Collector 一道01背包模板题，套模板即可
Read moreURAL - 1244 Gentlemen(01背包+记录路径)
URAL - 1244 Gentlemen 一道01背包的题目，只不过这一次不是用01背包来求最大值或最小值，而是将背包填满。这只需要将数组dp[]的dp[0]设为0，将其他设为 -∞即可（原因：这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。） 难点在于记录路径，同时处理多个解的情况。一开始我也想不到要怎么处理多个解的情况(总不能做两次dp..
Read moreAizu - ALDS1_1_D-Maximum Profit（转化思想+DP）
Aizu - ALDS1_1_1_D (这貌似是个日本的oj？名字叫aizu有点奇怪呢hhhh)
Read moreHDU1171-Big Event in HDU（多重背包做法）
HDOJ1171 这道题之前是用01背包做的，现在用多重背包的做法解决。这其实更符合题意（个人认为）
Read more
HDU4054-Hexadecimal View
Hexadecimal View 此题没有考查任何一个算法知识点，只是一道用来练代码熟悉度的题目
Read more拓展欧几里得算法
普通的欧几里得算法 这大概是最为人熟知的数论算法了吧，作用是求出gcd(a,b)，代码如下:
Read more
卢卡斯定理与中国剩余定理
卢卡斯定理 卢卡斯定理主要是用来求组合数取模，即C(n,m)%p。其适用范围是:组合数很大，但p又不是很大且p是素数的情况(10^6+3也算是“不很大”) 。卢卡斯定理可以表达为:
Read more快速乘算法
原理与快速幂相似，利用二进制将两个数的乘法运算转化为加法运算。具体代码如下:
Read more