动态规划

动态规划

状态设计

1，状态设计->拆分or合并
2，利用二分减少状态
3，状态分段

例题

Bzoj 2298
解：每个人的话相当于排名$[a_{i}+1,n-b_{i}]$,如果两个人的话代表的区间
有心爱那个键但不完全重合，那个这两个人冲突
那么就变成了选择最多不想交线段<->
Bzoj 1190
解：质量大的背包，观察数据性质考虑->吧状态数值变小，
对于b相同的数据分组dp，对于每一组分别转移，态数值变小
Cover ：
给定n个点无根树，节点i权值为$w_i$，若选择i，则可以将距离这个点$w_i$以内的点全部覆盖，任意一边的长度为1
问：最少选多少点能将整棵树覆盖$（n<=100）$

数位DP

sdoi 201

3 淘金

Bzoj 3329

x xor (x<<1+x)=(x<<1)->
(x<<1) + x = x xor (x<<1);
问题转化为一个数的二进制形式中没有相邻的1
"^"->不进位加法

期望，概率dp

1，求一些限制条件下的概率\期望
2，求概率常常为正推，期望常常为逆推
3，有拓扑序问题直接Dp，没有拓扑问题高斯消元是常见法
4，期望可加
5，全概率公式，贝叶斯公式

dp of dp

给出一个n*n的棋盘，上面有一些格子必须是黑色的，其他可以染黑或染白，求有多少种染色方法使得棋盘上的最大白色正方形边长为k
dp of dp

斯坦拿树

Bzoj 3205

预处理每个地方向每个方向推动到达哪里
令f[l][r][x][y]表示在点（x，y）将编号在[l,r]区间内放入机器人全部合并最小推动次数
推动：。。。。
利用<斯坦拿树>用途（spfa）跑最短路进行转移

斜率优化：

方程类似f[i]=min(f[j]+a[i]+b[j]+c[i]*d[j]+e)
去掉常数和只与i相关的变量
f[i]=min(c[i]*d[j]+(d[i]+b[j]))
与直线方程b=kx+y
最大/最小化截距
这样的点一定在凸壳上
维护凸壳在凸壳上找到最优决策

凸函数优化

IOI 2016 Alien

1<>将对角线以下的点翻到对角线以上
除去被包含的点，剩余的点按照x从小到大排序，y一定也是从小到大的
，且一个正方形会覆盖连续一断点
令f[i][j]表示用了i个正方形，覆盖了前j个点的最小总面积
转移枚举最后一个正方形覆盖的是哪一段点
f[i][j]=min{$f[i-1][k]+y_i-x_k+1)^2-max(0,y_k,x_{k+1}+1)^2$}
斜率优化->用栈维护，复杂度O(nk),60%;
2<>若不限制选取的小正方形的个数，而是改为每多选取一个小正方形就需要额外的C的面积
g(j)表示覆盖钱j个点的最小面积
g(j)=min{f[k][j]+kC}
g(j)=min{$g（k)+(y_j-x_{k+1}+1)^2-max(0,y_k-x_{k+1}+1)^2+C$}
g(n)可以用斜率优化在限行时间内求出，并可以同时求出此时最少需要的最小正方形数
通过g（n）求出对应的f[x][n]的值

杂题选讲

int main() {
    using namespace std;
    return null;    
}

TC SRM563-950

考虑两个格子之间的关系，如果两个硬币在这两个格子上，是否有机会调出
->记忆化搜索两个格子

TC SRM564-850

对于前面的b随便取，最有一个b一定能调整使得异或和为n
然而有$A_i$的限制
将$A_i$排序，对于最大的元素$A_1$，考虑$B_1$在$A_1$的最高位的二进制是否取1
$/....................................................................../$

Bzoj 3080

枚举边权总和->枚举平均数->计算生成树每条边对方差的贡献->完
NEERC 2017-2018 Moscow