2019-10-01笔记
贪心
贪心算法是指，贪心算法是指，在对问题求解时总做出当前看来最好的选择。 贪心算法是指，在对问题求解时总做出当前看来最好的选择。 也就是说，不从整体最优上加以考虑他所做出的在某种意义局 也就是说，不从整体最优上加以考虑他所做出的在某种意义局部最优解。
P1080
一看最大值最小先想二分。
我们考虑两个相邻的人$x$和$y$，看交换他们是否会变得更优。
设$S=a_1 a_2⋯a_{x-1}$，则$v_{x_1}=\lfloor\cfrac{S}{b_x}\rfloor,v_{y_1}=\lfloor\cfrac{Sa_x}{b_y}\rfloor$。
如果把这两个人交换一下，那么 $v_{x_2}=\lfloor\cfrac{S_{a_y}}{b_x}\rfloor,v_{y_2}=\lfloor\cfrac{S}{b_y}\rfloor$。
除了这两个人之外，其他所有人的奖赏都不会发生改变，所以我们只需要考虑$max(v_{x_1},v_{y_1})$和$max(v_{x_2},v_{y_2})$的大小关系即可。
而我们发现$v_{x_1} \leq v_{x_2},v_{y_2} \leq v_{y_1}$，所以我们其实只需要比较$v_{x_2}$和$v_{y_1}$。
$v_{x_2}<v_{y_1} \rightarrow \cfrac{S_{a_y}}{b_x} \lt \cfrac{S_{a_x}}{b_y} \rightarrow a_yb_y<a_x b_x$（下取整其实不影响结果）
也就是说$a_i b_i$较小的要排在前面。
所以直接按照$a_ib_i$排序就可以了。注意统计答案需要高精度。
P3045
- 能用优惠卷一定用。
- 能买便宜就不买贵。
- 先取$C_i$最小的前$k$个作为答案，这一部分物品定会在最终的答案里。
然后我们考虑用剩下的钱买物品。分两种情况：
- 下一个不用优惠卷则补偿差价$p_i$
- 下一个用优惠卷，答案加上$c_i+min(p_j-c_j)$
CF1214C
移动左括号等价移动右括号。
当然，也可以把最左边的右括号移动到最右，判断时候合法。
$$Ans=\sum_{i=1}^k(S_{p_i}-S_{p_{i-1}})=S_{p_1}+2P_2-2S_{p_1}+3S_{P_3}-3S_{p_2}+\cdots+kS_{p_k}-kS_{p_{k-1}}=kS_n-\sum_{i=1}^{k-1}S_{p_i}$$
也就是说我们只需要把整个数组求一前缀和，然后在$n−1$个里面选 个里面选择最大的$k−1$个减去，得到的就是最小值。
CF1213F
考虑拓扑排序。
套路
考虑相邻两个元素，看交换它们是否会使得答案变更优。 经典模型是你需要按照一定顺序考虑所有的元素，决最后答案。 经典模型是你需要按照一定顺序考虑所有的元素，决定最后答案。
如果发现贪心发现原来的策略不是最优，可以考虑实现可以撤销的贪心。
二分
二分有二分查找，二分答案等。
P2698
二分区间长度，然后单调队列扫。
搜索
枚举全排列
时间复杂度：$O(n!)$
int a[15];
bool flag[15];
void dfs( int step ) {
if ( step > n )
return;
for ( int i = 1; i <= n; i++ ) {
if ( flag[i] )
continue;
a[step] = i;
flag[i] = 1;
dfs( step + 1 );
flag[i] = 0;
}
}枚举子集
时间复杂度：$O(2^n)$
void dfs( int step ) {
if ( step > n )
return;
flag[step] = 1;
dfs( step + 1 );
flag[step] = 0;
dfs( step + 1 );
}
for ( int s = 0; s < ( 1 << n ); s++ ) {
//do something.
}枚举子集的子集
时间复杂度：$O(3^n)$
for ( int s = 0; s < ( 1 << n ); s++ )
for ( int t = s; t; t = ( t - 1 ) & s ) {
//do something.
}其他提及的内容
multiset- 0/1分数规划
- 参见0/1分数规划
版权声明：本文是原创文章，版权归 星雾月雨 所有。
本文链接：https://www.ariels.xyz/archives/478.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。
