动态规划(DP)做题记录

· · 个人记录

P2467 [SDOI2010]地精部落

知道做到这道题我才知道, 原来小范围内的组合数还可以用杨辉三角求。

详见博客文章：杨辉三角求组合数

以下几条性质摘自其中：

杨辉三角的性质：

1.第n行的元素个数有n个；

2.第n行的所有元素之和为2（n-1)；

3.第n行第m个数的值为C(n-1, m-1)，其中C为组合数；

4.（a+b)^n 展开后的各项系数等于第n+1行的值；

5.第n行第m个数的奇偶判断，及C（n-1,m-1)的奇偶判断：
（m-1)&(n-1)==(m-1)? 奇 ： 偶；
————————————————

版权声明：本文为CSDN博主「pcrango」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/pcfbyssz/article/details/81874796

记录一个神奇的现象：P4095 [HEOI2013]Eden 的新背包问题

我只是逐渐开大f[i][j]中j（花费）枚举的范围，然后就75(WA5) -> 95(WA1) -> 95(WA1) -> 100 -> 80(MLE4)，非常神奇。

数位DP板子：

基本模式为记忆化搜索，方便起见，work函数写个for再写个islim = true的特判（暂且这么叫）。记得把0的情况给判掉。


//P2657 [SCOI2009]windy数
int len, num[N];
ll f[N][N];
//f[i][j]:一般情况下，考虑到（从低位向高位）第i个数字，前一个数字为j的方案数 (不含0) 
ll dp(int cur, int lst, bool islim, bool is0) {
    if (cur == 0 && is0)    return 0;
    if (!islim && !is0 && f[cur][lst])  return f[cur][lst];
    if (cur == 0)   return 1;
    ll res = 0;
    int limi = islim ? num[cur] : 9;
    for (register int i = 0; i <= limi; ++i) {
        if (!is0 && abs(i - lst) < 2)   continue;
        res += dp(cur - 1, i, islim && i == limi, is0 && i == 0);
    }
    if (!islim && !is0) f[cur][lst] = res;
    return res;
}
inline ll work(ll x) {
    memset(num, 0, sizeof(num));
    len = 0;
    while (x)   num[++len] = x % 10, x /= 10;
    ll res = 0;
    for (register int i = 0; i < num[len]; ++i) {
        res += dp(len - 1, i, 0, i == 0);
    }
    res += dp(len - 1, num[len], 1, 0);
    return res;
}

期望DP典型例题：P4316 绿豆蛙的归宿

由于大量随机变量等数学元素的掺入，期望DP问题的解决常常艰难而又复杂，这也是我不敢做期望DP题，至今(2020.1.20)才AC第一道期望DP题的原因之一。

然而我终将难以逃过期望DP的折磨，我还是做了一道典型题：P4316 绿豆蛙的归宿：

题意：
给一张有源汇（暂且这么叫）的DAG，边有边权。
每个出度为d的节点有1/d的概率走向其任意一条出边。
求源点到汇点的期望路径长。
n <= 1e5, m <= 2e5

如果按正图建的话，是不对的。

我们以建反图的思路来做这道题。

定义f[i]为i->n的期望路径长，这样有（正图中）f[u] = Σ(u->v) ( (f[v] + len(u->v)) * P(u->v) )

让后利用反图拓扑序解决此问题。

补充：为什么正推不对？

要非得用正推，只好f[i]为1->i的期望。正反对比如下图（左逆推右顺推）（最下面的字母不用管）：

这样，我们不得不记录起点到当前点i的概率P[i]，不是那么好做。（但好像也可做）。

具体可见：题解 P4316 【绿豆蛙的归宿】

//p,d初始时都是出度
while (front < rear) {
    cur = que[++front];
    for (register int i = head[cur]; i; i = e[i].nxt) {
        to = e[i].to;
        f[to] += 1.0 * (f[cur] + e[i].val) / p[to];
        if (!(--d[to])) que[++rear] = to;
    }
}

斜率优化

斜率优化是个难点，或许做多了就好了吧。

还是和各种DP优化一样，我们先想出比较暴力的转移方程：f[i] = max{f[j] + xxx}，如果发现xxx里有i的相关项与j的相关项相乘的话，就可能是斜率优化了。

我们通常以j的相关项为横坐标，f[j]为纵坐标，把候选决策集合（点集）表示出来，再把f[j]用j的相关项和i的相关项表示出来，如果发现f[j] = xxx是斜率已知的直线，纵截距代表f[i]，那么用斜率优化就基本没错了。

例题：301. 任务安排2

正好遇到这道题就说一下：如果某个状态进行某种决策后，其对后的影响已知，不妨让状态顺便包含一下该影响。这种思想叫“费用提前计算”（by lyd)

如这道例题，状态f[i]如果表示将前i件任务分批处理所需最小费用（含S对以后的影响），那么这道题将由n³降到n²。

代码：

struct vectors{
    int x;
    int y;
    vectors(int xx = 0, int yy = 0){x = xx, y = yy;}
    vectors operator +(const vectors a)const {
        return vectors(x + a.x, y + a.y);
    }
    vectors operator -(const vectors a)const {
        return vectors(x - a.x, y - a.y);
    }
    int operator *(const vectors a)const {
        return x * a.y - y * a.x;
    }
}q[N << 2], xl;
int main() {
    ...
    for (register int i = 1; i <= n; ++i) {
        tmp = s * csum[n] + tsum[i] * csum[i];
        f[i] = tmp;
        xl = vectors(1, s + tsum[i]);
        while (front + 1 < rear && (q[front + 2] - q[front + 1]) * xl >= 0) front++;
        if (front < rear)   f[i] = min(f[i], tmp + q[front + 1].y - q[front + 1].x * (s + tsum[i]));
        xl = vectors(csum[i], f[i]);
        while (front < rear - 1 && (q[rear] - q[rear - 1]) * (xl - q[rear - 1]) <= 0)   rear--;
        q[++rear] = xl;
    }

    printf("%lld\n", f[n]);
}

注意！！

写正常斜率优化的第二个While(取答案）时，一定记得... * (xl - q[rear - 1])而不是... * xl！！（计算几何没学好）

果然计算几何没学好

斜率优化的第二个While（取答案）时，是(stk[] - stk[]) * xl而不是(stk[] - stk[]) * (stk[] + xl)！！！

注意斜率是 xl(1, ...)，而不是 xl(...)。

注意计算几何要用 <= 而不要用 <。

决策单调性优化DP

不会用四边形不等式判断，还是打表判断吧。

例题：P1912 [NOI2009]诗人小G

维护三元组单调队列<l, r, pos>，pos为[l,r]内的决策点。由于有决策单调性，队列里的区间和决策点都是单调递增的。

此题型的大致过程如下：

for (int i = 1; i <= n; ++i) {
    if (队列非空 && 队头右端点比i小)   弹掉队头
    else    修改队头的l
    用队头计算f[i]

    if (i -> n 不如 队尾决策点 -> n 优） continue;
    while (队列非空 && i -> 队尾左端点 优于 队尾决策点 -> 队尾左端点）    弹队尾
    if (队空） 添加节点(i, n, i)于队尾
    else {
        查找x = 队尾区间中 i占优势的第一个点（可能为r+1）
        修改队尾右端点
        新增节点(x, n, i)
    }
}

Code：

inline ll calc(int j, int i)//计算用j来转移i
inline int half_find(node nod, int i)
//返回x = nod的区间中 i占优势的第一个点（可能为r+1）
...
//main()中
q[++rear] = (node){1, n, 0};
for (register int i = 1; i <= n; ++i) {
    if (front < rear && q[front + 1].r < i) front++;
    else    q[front + 1].l = i + 1;
    register int pos = q[front + 1].pos;
    f[i] = calc(pos, i);
    pre[i] = pos;
    //计算
    //-------
    //插入i
    if (calc(i, n) >= calc(q[rear].pos, n)) continue;
    while (front < rear && calc(q[rear].pos, q[rear].l) >= calc(i, q[rear].l))
        rear--;
    if (front >= rear) {
        q[++rear] = (node){i, n, i};
        continue;
    }
    int x = half_find(q[rear], i);
    q[rear].r = x - 1;
    q[++rear] = (node){x, n, i};
}

细节特别多，该不该算上等于，各种特判，各种初始化一定要注意！