皮特有 n 根烟 , 有一个兑换数 k. 皮特每抽 一根烟都把烟头留着 , 直到足够 k 个烟头时 , 就可以换一根新烟抽 . 要编写一个程序 , 输入 n,k, 算出皮特最多能抽多少烟 .
sum = n; while (n / k) { sum += n / k; n = n / k + n % k; }
句进行估算。
FOJ1319 Blocks of Stones
经典的石子归并问题 有 n (1<=n<=100) 堆石子，现要将石子 有次序地合并成一堆 . 规定每次只能选取相 邻的两堆合并成新的一堆，并将新的一堆 的石子数，记为该次合并的得分。求最少 的得分。 例如： 3 堆石子 2 5 1 合并方案一 : [2 5 1]->[7 1]->[8] 分数 7+8=15 合并方案二 : [2 5 1]->[2 6]->[8] 分数 6+8=14
Ones
How to improve? For multiply, 1<j*j<i. f[i]=min{f[j]+f[i/j]+f[i%j]} 1<j*j<i O(n1.5) 1<=n<=10000
n1.5=1,000,000 算法时间可以以计算机每秒执行 8,000,000 语
Ones
让 f[i] 表示最少数量的 1 能够表示 i 。 add: f[i]=f[j]+f[i-j] 0<j<i multiply: f[i]=f[j]+f[i/j] 0<j<i, i%j=0 for(i=1;i<=n;i++){ f[i]=i; for(j=1;j<i;j++){ f[i]=min(f[i],f[j]+f[i-j]); if (i%j==0) f[i]=min(f[j]+f[i-j]); } } O(n2) n<=10000
FOJ1319 Blocks of Stones
状态表示： 用 a[i] 表示初始时每堆石子的个数。 用 s[i] 表示初始时从第 1 堆到第 i 堆石子的总 和。 用 f[i][j](i<=j) 表示从第 i 堆合并到第 j 堆的最 小分数。 f[i][j]=min{f[i,k-1]+f[k,j]}+w[i,j]; w[i][j]=sum{a[i]…a[j]}=s[j]-s[i-1]; 这样枚举是 n^3 的。
9 10 11 12 13 14
若被检查的活动 i 的开始时间 Si 小于最近 选择的活动 j 的结束时间 fi ，则不选择活动 i ，否则选择活动 i 加入集合 A 中。 可以证明，如果在可能的事件 a1<a2<… <an 中选取在时间上不重叠的最长序列， 那么一定存在一个包含 a1 （结束最早）的 最长序列。
动态规划源代码
#include<cstdio> const int M=1000+5; int f[M][M],a[M][M]; inline int max(int x,int y){ return x<y?y:x; } int main(){ int i,j,n; while(scanf("%d",&n)==1){ for(i=1;i<=n;i++) for(j=1;j<=i;j++) scanf("%d",&a[i][j]); for(j=1;j<=n;j++) f[n][j]=a[n][j]; for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]); printf("%d\n",f[1][1]); } return 0; }
8 8
9 8
10 11 2 12
10 11 12 13 14
所以做多可以容纳 4 个活动
代码 :
int greedySelector(int *s, int { a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } *f, bool *a)
FOJ1004 Number Triangle
求人从顶端到底部 , 每次只能向左下右下走 , 最 多能取得的值 .
数据规模 : 行数 1<=R<=1000 数塔中数 值 0..100 如图最优解为 [ 7-3-8-7-5 ]=30
状态表示 用 a[i][j] 表示第 i 行第 j 列的值。 用 F(i,j) 表示第 i 行第 j 列走到底部所能取得的最大值。 而 F(1,1) 就是题目所求的答案 。
搜索源代码
#include<cstdio> const int M=1000+5; int a[M][M],n; inline int max(int x,int y){ return x<y?y:x; } int f(int i,int j){ if (i==n) return a[i][j]; else return a[i][j]+max(f(i+1,j),f(i+1,j+1)); } int main(){ int i,j; while(scanf("%d",&n)==1){ for(i=1;i<=n;i++) for(j=1;j<=i;j++) scanf("%d",&a[i][j]); printf("%d\n",f(1,1)); } return 0; }
1672Minimum Adjacent Value
• The minimum adjacent value is the minimum
absolute value |a - b| of the two different elements a and b in the array.
If the N elements are all the same, just output the absolute value of the element.
FOJ 1085 Work Reduction
给出初始时的工作量 n ，结束时剩下的工 作量 m ，给出可以完成这些工作量的公司 ，这些公司的收费方式有两种， A 一种是 减少一个单位的的工作量，每减少一单位 工作量花费 a ， B 一种是减少一半单位的 工作量，总的花费为 b ，问，分别由这些 公司完成的最小的费用。
FOJ1320 Ones
给一个整数 n ，要你找一个值为 n 的表达 式，这个表达式只有 1 + * ( ) 够成。并且 1 不能连续，比如 11+1 就不合法。 输入 n,(1<=n<=10000) 输出最少需要多少个 1 才能构成表达式。 样例： n=2=1+1 ans=2 n=10=(1+1)*(1+1+1+1+1) ans=7
若要用贪心算法求解某问题的整体最优解 ，必须首先证明贪心思想在该问题的应用 结果就是最优解！！
1316Tian Ji -- The Horse Racing 1541Exploration 1505Minimum value
动态规划 （ Dynamic Programming ）
贪心算法并不总能求得问题的整体最优解。 但对于活动安排问题，贪心算法 greedySelector 却总能求得的整体最优解 ，即它最终所确定的相容活动集合 A 的规 模最大。这个结论可以用数学归纳法证明 。
i S[i ] f[i]
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6
• 动态规划算法的基本要素 • （ 1 ）最优子结构性质 • （ 2 ）重叠子问题性质 • 掌握设计动态规划算法的步骤。 • (1) 找出最优解的性质，并刻划其结构特征。 • (2) 递归地定义最优值。（写出动态规划方程）； • (3) 以自底向上的方式计算出最优值。 • (4) 根据计算最优值时得到的信息，构造最优解。
Nlog(N) 排序 求相邻的两个数的差的绝对值 , O(N) 扫描求出最小值 It is guaranteed that the element in the array will fit within a 32-bit signed integer. |a-b| 超过 32 位整型 64 位整型 Long long
最长公共子序列问题 LCS
最长公共子序列问题也有最优子结构性质，因为我们有如 下定理： 定理 : LCS 的最优子结构性质 设序列 X=<x1, x2, …, xm> 和 Y=<y1, y2, …, yn> 的一个 最长公共子序列 Z=<z1, z2, …, zk> ，则： 若 xm=yn ，则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的最 长公共子序列； 若 xm≠yn 且 zk≠xm ，则 Z 是 Xm-1 和 Y 的最长公共子序 列； 若 xm≠yn 且 zk≠yn ，则 Z 是 X 和 Yn-1 的最长公共子序 列。 其中 Xm-1=<x1, x2, …, xm-1> ， Yn-1=<y1, y2, …, yn-1> ， Zk-1=<z1, z2, …, zk-1> 。
