贪心算法是从问题的初始状态出发,通过若干次的贪心选择而得到的最优值(或较优值)。
贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,至于当前状态有关。
适用前提是,局部最优策略能导致全局最优策略。
n n n 个物体,第 i i i 个物体重量为 w i w_i wi,价值为 v i v_i vi,选择物体,每一个物体可以只取走一部分,使得总重量不超过 S S S 且总价值尽量高。
贪心策略:先选出性价比高的。
n n n 个人,第 i i i 个人重量为 w i w_i wi,每艘船载重量为 C C C,最多可乘两人。用最少的船装载所有人。
贪心策略:最轻的人和最重的人配对。
将区间按照右端点的先后顺序排序,依次取每个区间的右端点(因为右端点可以覆盖尽量多的线段),递归操作即可。
给 n n n 个闭区间 [ a i , b i ] [a_i,b_i] [ai,bi],选择尽量少的区间覆盖一条指定的线段区间 [ s , t ] [s,t] [s,t]。
将所有区间的左端点从大到小排序,每次选择覆盖点 s s s 的区间中右端点坐标最大的一个,并将 s s s 更新为该区间的右端点坐标,直到选择的区间包含 t t t 为止。
一种应用于加工生产调度问题的贪心策略。
我们先考虑两个物品 { a 1 , b 1 } , { a 2 , b 2 } \{a_1,b_1\},\{a_2,b_2\} {a1,b1},{a2,b2},先假定在 A 机器上,1 物品比 2 物品先加工,上图中的 1 和 2 分别是作业 2 在 B 机器上加工有 / 无等待的情况。
显然有 T min = a 1 + b 1 + a 2 + b 2 − min ( b 1 , a 2 ) T_{\min}=a_1+b_1+a_2+b_2-\min(b_1,a_2) Tmin=a1+b1+a2+b2−min(b1,a2)(相当于减掉两机器同时加工物品的情况)。对于 2 物品比 1 物品先在 A 机器加工的的情况,有 T min = a 1 + b 1 + a 2 + b 2 − min ( a 1 , b 2 ) T_{\min}=a_1+b_1+a_2+b_2-\min(a_1,b_2) Tmin=a1+b1+a2+b2−min(a1,b2),所以按照 min ( b 1 , a 2 ) , min ( a 1 , b 2 ) \min(b_1,a_2),\min(a_1,b_2) min(b1,a2),min(a1,b2) 的大小降序排序即可。
预处理 O ( m n ) O(mn) O(mn)
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
s[i][j]
:第
i
i
i 行
j
j
j 列格左上部分所有元素的和。
以
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1) 为左上角,
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2) 为右下角的子矩阵的和为:
s
(
x
2
,
y
2
)
−
s
(
x
1
−
1
,
y
2
)
−
s
(
x
2
,
y
1
−
1
)
+
s
(
x
1
−
1
,
y
1
−
1
)
s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)+s(x_1-1,y_1-1)
s(x2,y2)−s(x1−1,y2)−s(x2,y1−1)+s(x1−1,y1−1)
首先给定一个原数组
a
a
a:
a
1
,
a
2
,
a
3
,
⋯
,
a
n
a_1,a_2,a_3,\cdots,a_n
a1,a2,a3,⋯,an,然后我们构造一个数组
b
b
b:
b
1
,
b
2
,
b
3
⋯
,
b
i
b_1,b_2,b_3\cdots,b_i
b1,b2,b3⋯,bi,使得
a
i
=
b
1
+
b
2
+
b
3
+
⋯
+
b
i
a_i=b_1+b_2+b_3+\cdots+b_i
ai=b1+b2+b3+⋯+bi。
也就是说,
a
a
a 数组是
b
b
b 数组的前缀和数组,反过来我们把
b
b
b 数组叫做
a
a
a 数组的差分数组。换句话说,每一个
a
i
a_i
ai 都是
b
b
b 数组中从头开始的一段区间和。
一维差分
给
a
a
a 数组中的
[
l
,
r
]
[l,r]
[l,r] 区间中的每一个数都加上
c
c
c,只需对差分数组
b
b
b 做 b[l]+=c,b[r+1]-=c
。时间复杂度为
O
(
1
)
O(1)
O(1)。
s[x1][y1]+=c,s[x2+1][y1]-=c,s[x1][y2+1]-=c,s[x2+1][y2+1]+=c;
卡特兰数,又称卡塔兰数(Catalan Number),是组合数学中一个常用的数列。其前几项为: 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , ⋯ \boxed{1,2,5,14,42,132,429,1430,4862,\cdots} 1,2,5,14,42,132,429,1430,4862,⋯
f ( n ) = ∑ i = 0 n − 1 f ( i ) × f ( n − i − 1 ) f(n)=\sum_{i=0}^{n-1}f(i)\times f(n-i-1) f(n)=∑i=0n−1f(i)×f(n−i−1)
f ( n ) = f ( n − 1 ) × ( 4 × n − 2 ) n + 1 f(n)=\dfrac{f(n-1)\times(4\times n-2)}{n+1} f(n)=n+1f(n−1)×(4×n−2)
卡特兰数的组合数学公式,详见组合数学。
基数排序,是桶排序的扩展。它的基本思想是,把整数按位切割,从低位到高位排序。
具体实现就是将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后从最低位开始,依次进行一次排序。从最低位排序到最高位排序完成以后,数列就变成一个有序序列。