动态规划

数位dp

数位dp是一种经典的dp模型，它的主要应用场景是与大整数及其数码有关的问题。这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 $10^{18}$），暴力枚举验证会超时。

数位dp的主要思想是，把大整数看成一个由 $0 \sim 9$ 构成的整数序列而不是一个数。并采用序列 dp 的方式，从高位到低位一位一位地 dp。

例题1：洛谷P2657 [SCOI2009] windy 数

[SCOI2009] windy 数
题目背景
windy 定义了一种 windy 数。

题目描述
不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

输入格式
输入只有一行两个整数，分别表示 $a$ 和 $b$。

输出格式
输出一行一个整数表示答案。

样例 #1
样例输入 #1
1
1 10
样例输出 #1
1
9
样例 #2
样例输入 #2
1
25 50
样例输出 #2
1
20
提示
数据规模与约定
对于全部的测试点，保证 $1 \leq a \leq b \leq 2 \times 10^9$。

分析：

经典数位dp的要素：求 $l$ 到 $r $之间的符合限制的数的个数（或求和），通常这个限制与数位有关。

首先，对于求 $l \le x \le r$ 的 $x$ 的个数，我们将其转化为求 $0 \le x \le r$ 的个数减去 $0 \le x \le l − 1$ 的个数。显然这两个$x$ 个数的求法是一样的，因此接下来只需要考虑 $x \le r$ 的求法。

梳理一下目前的限制：$\le r$，没有前导 0，相邻数位差至少为 2。看起来限制有三个，较为复杂，但我们可以观察到一点，前两个限制都是按从高位到低位的顺序确定的，第三个限制从低位到高位和从高位到低位均可。

因此，我们考虑从高位到低位逐位进行 dp，在 dp 的过程中维护上述限制。

我们令 $f[i][j][lim][zero]$表示目前已经确定了前 $i$ 高的数位的值，最后一位（第 $i$ 高位）的值为 $j$。$lim$ 和 $zero$ 是两个布尔值， $lim = 0$ 表示只考虑前 $i$ 位有 $x < r$，$lim = 1$ 表示前 $i$ 位 $x = r$。 $zero = 0$ 表示当前 $i$ 位中已有非 $0$ 元素，$zero = 1$ 表示当前 $i $位全为 $0$。这个状态的最后两位 $lim$ 和 $zero$ 对应了 $x \le r $和没有前导 $0 $这两个限制。

在 dp 转移的时候，直接枚举下一位的值 $k$。

对于 $f[i][j][lim][zero]$，如果 $zero \not = 0$，则下一位与 $j$ 至少相差 $2$；

1	if(!zero&&abs(j-k)<2) continue;

如果 $lim = 1$，则下一位需不超过 $r$ 的对应位。

1	if(lim&&k>a[i+1]) continue; //a[i] 表示 r 第 i 位的值

通过下一位的值可以得到新的 $lim’$ 和 $zero’$，因此可以进行 dp 转移。

代码：

#include<bits/stdc++.h>
using namespace std;

int l,r;
int len;
int f[20][20][3][3];//已填位数，当前数值，前几位是否为最大，是否有有效位
int a[20];

int dp(string r){
    int res=0;
    memset(a,0,sizeof a);
    len=r.length();
    for(int i=0;i<len;i++){
        a[i+1]=r[i]-'0';
    }
    memset(f,0,sizeof f);
    f[0][0][1][1]=1;
    for(int i=0;i<len;i++){
        for(int j=0;j<=9;j++){
            for(int lim=0;lim<2;lim++){
                for(int zero=0;zero<2;zero++){
                    for(int k=0;k<=9;k++){
                        if(zero==0&&abs(k-j)<2)continue;
                        if(lim==1&&k>a[i+1])break;
                        f[i+1][k][lim&&k==a[i+1]][zero&&!k]+=f[i][j][lim][zero];
                        
                    }
                }
            }
        }
    }
    for(int j=0;j<=9;j++){
        for(int lim=0;lim<2;lim++){
            res+=f[len][j][lim][0];
        }
    }
    return res;
}

int main(){
    cin >> l >> r;
    l--;
    string ls,rs;
    while(l){
        char ch=l%10+'0';
        ls=ch+ls;
        l/=10;
    }
    while(r){
        char ch=r%10+'0';
        rs=ch+rs;
        r/=10;
    }
    cout << dp(rs)-dp(ls);
    return 0;
}

例题2：洛谷P4124 [CQOI2016] 手机号码

[CQOI2016] 手机号码
题目描述
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。

工具需要检测的号码特征有两个：号码中要出现至少 $3$ 个相邻的相同数字；号码中不能同时出现 $8$ 和 $4$。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。

手机号码一定是 $11$ 位数，且不含前导的 $0$。工具接收两个数 $L$ 和 $R$，自动统计出 $[L,R]$ 区间内所有满足条件的号码数量。$L$ 和 $R$ 也是 $11$ 位的手机号码。

输入格式
输入文件内容只有一行，为空格分隔的 $2$ 个正整数 $L,R$。

输出格式
输出文件内容只有一行，为 $1$ 个整数，表示满足条件的手机号数量。

样例 #1
样例输入 #1
1
12121284000 12121285550
样例输出 #1
1
5
提示
样例解释：满足条件的号码： 12121285000、 12121285111、 12121285222、 12121285333、 12121285550。

数据范围：$10^{10}\leq L\leq R<10^{11}$。

状态压缩dp

状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

例题1：洛谷P3052 [USACO12MAR] Cows in a Skyscraper G

[USACO12MAR] Cows in a Skyscraper G
题面翻译
给出 $n$ 个物品，体积为 $w _ 1, w _ 2, \cdots, w _ n$，现把其分成若干组，要求每组总体积小于等于 $W$，问最小分组数量。

$n\le 18,1\le c_i\le W\le 10^8$。

题目描述
A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don’t like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.

输入格式
* Line 1: N and W separated by a space.

* Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.

输出格式
* A single integer, R, indicating the minimum number of elevator rides needed.

one of the R trips down the elevator.

样例 #1
样例输入 #1
1
2
3
4
5
4 10 
5 
6 
3 
7
样例输出 #1
1
3
提示
There are four cows weighing 5, 6, 3, and 7 pounds. The elevator has a maximum weight capacity of 10 pounds.

We can put the cow weighing 3 on the same elevator as any other cow but the other three cows are too heavy to be combined. For the solution above, elevator ride 1 involves cow #1 and #3, elevator ride 2 involves cow #2, and elevator ride 3 involves cow #4. Several other solutions are possible for this input.

分析：

首先我们有一个最朴素的暴搜想法，就是每次枚举一个物品，如果它可以被加入当前组中就直接加入，否则另开一个新的组。

这个暴搜显然是无法通过 $n \le 18$ 的，因此我们要找到这个问题中 “对答案贡献相同的情况”，然后想办法改用 dp 处理。

在这个问题中，我们可以发现，每一组的内部元素的加入顺序是无关的，组与组之间的顺序也是无关的。如果我们用搜索，则相当于枚举了所有可能的顺序，产生了极大的时间浪费。

因此，我们可以以此为突破口进行 dp，把物品的集合作为 dp 的状态，然后进行转移。

令 $f[S]$ 表示集合 $S$ 的物品至少要分成几组，$sum[S]$ 表示集合 $S$ 中所有物品的体积和。在计算 $f[S]$ 时，我们枚举 $S$ 的一个非空子集 $T$，如果 $sum[T]<=W$，则可以令 $f[S] = min(f[S], f[S \setminus T] + 1)$。（$S \setminus T$ 表示从集合 $S$ 中去除集合 $T$ 后剩下的集合）

当我们要把一个集合作为 dp 的状态时，我们可以用一个二进制数来描述集合。

例如 $S$ 是一个 ${ 1, 2, . . . , n}$ 的一个子集，那么我们可以用一个 $[0, 2^n )$ 的整数 $st$ 来表示 $S$。$st$ 在二进制下从低到高的第 $i$ 位为 $1$ 表示 $S$ 中有 $i + 1$ 这个元素，为 $0$ 表示没有 $i + 1$ 这个元素。

在用二进制数表示集合后，我们可以用位运算来实现集合运算。我们设 $s$ 为表示集合 $S$ 的二进制数，$t$ 为表示集合 $T$ 的二进制数，则有：

$S ∪ T$ 可以用 $s|t$ 表示
$ S ∩ T$ 可以用 $s&t$ 表示
当 $T ⊂ S$ 时，$S \setminus T$ 可以用 $s \textasciicircum t$ 或者 $s-t$ 表示
$S$ 中是否有元素 $i$ 可以用 $(s>>i-1)&1$ 表示
$T$ 是否为 $S$ 的子集可以用 $(s&t)==t$ 表示
$S$ 的补集可以用 $((1<<n)-1)\textasciicircum s$ 表示（$n$ 为全集大小）

大量出现位运算时建议使用括号，避免因为运算符优先级问题浪费大量调试时间。

可以使用$__builtin_ctz(i)$计算后缀$0$，$__builtin_clz(i)$计算前缀$0$。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1<<18+5;

int n,W;
int f[N],sum[N];
int w[20];

int lowbit(int x){
    return x&-x;
}

int main(){
    cin >> n >> W;
    for(int i=1;i<=n;i++){
        cin >> w[i];
    }
    for(int i=1;i<1<<n;i++){
        sum[i]=min(W+1,w[__builtin_ctz(i)+1]+sum[i-lowbit(i)]);
    }
    for(int i=1;i<1<<n;i++){
        f[i]=n+1;
        for(int j=1;j<1<<n;j++){
            if((i&j)!=j)continue;
            if(sum[j]<=W)f[i]=min(f[i],f[i^j]+1);
        }
    }
    cout << f[(1<<n)-1];
    return 0;
}

时间复杂度$O(4^n)$，无法通过本题。

引理：令$S$为${1,2,\cdots,n}$的一个子集，$T$为$S$的一个子集，则不同的$(S,T)$对的个数为$3^n$

虽然需要枚举的 $S$ 和 $T$ 的总对数只有 $3^n$，但想要达到 $O(3^n)$ 的复杂度，还得确保代码中只枚举 $S$ 的子集。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1<<18+5;

int n,W;
int f[N],sum[N];
int w[20];

int lowbit(int x){
    return x&-x;
}

int main(){
    cin >> n >> W;
    for(int i=1;i<=n;i++){
        cin >> w[i];
    }
    for(int i=1;i<1<<n;i++){
        sum[i]=min(W+1,w[__builtin_ctz(i)+1]+sum[i-lowbit(i)]);
    }
    for(int i=1;i<1<<n;i++){
        f[i]=n+1;
        for(int j=i;j;--j&=i){
            if(sum[j]<=W)f[i]=min(f[i],f[i^j]+1);
        }
    }
    cout << f[(1<<n)-1];
    return 0;
}

为了获得更优的复杂度，我们可以每次加入一个物品而不是一组物品。

令 $f[S]$ 表示加入了 $S$ 中的所有物品后的最优情况，此处最优情况指最小组数，在最小组数前提下最后一组的当前大小。不难发现这个二元组是可以比较优劣的，优先比较最小组数，最小组数相同时最后一组的当前大小越小越优。计算 $f[S]$ 时每次枚举一个 $S$ 中的元素 $i$，从 $f[S \setminus {i}]$ 中转移即可。

例题2：洛谷P1879 [USACO06NOV] Corn Fields G

[USACO06NOV] Corn Fields G
题目描述
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12, 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

农场主 $\rm John$ 新买了一块长方形的新牧场，这块牧场被划分成 $M$ 行 $N$ 列 $(1 \le M \le 12, 1 \le N \le 12)$，每一格都是一块正方形的土地。 $\rm John$ 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 $\rm John$ 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

$\rm John$ 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入格式
第一行：两个整数 $M$ 和 $N$，用空格隔开。

第 $2$ 到第 $M+1$ 行：每行包含 $N$ 个用空格隔开的整数，描述了每块土地的状态。第 $i+1$ 行描述了第 $i$ 行的土地，所有整数均为 $0$ 或 $1$ ，是 $1$ 的话，表示这块土地足够肥沃，$0$ 则表示这块土地不适合种草。

输出格式
一个整数，即牧场分配总方案数除以 $100,000,000$ 的余数。

样例 #1
样例输入 #1
1
2
3
2 3
1 1 1
0 1 0
样例输出 #1
1
9

概率dp

概率 dp 用于解决概率问题与期望问题。一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到高斯消元来优化。概率 dp 也会结合其他知识进行考察，例如状态压缩，树上进行dp转移等。

例题1：洛谷CF16E Fish/Codeforces 16E

Fish
题面翻译
题目描述

有n条鱼，编号从1到n，住在湖里。每天有一对鱼相遇，

彼此相遇的概率是一样的。如果两条标号为i和j的鱼见面，第一只吃了第二只的概率为$a_{i,j}$，第二只会吃了第一只的概率为$a_{j,i}$=$1-a_{i,j}$。所描述的过程继续进行，直到湖里只剩下一条鱼。请你算出每只鱼最后存活在湖里的可能性。

输入格式

第一行包含整数n( 1<=n<=18)–湖里的鱼数量。接下来n行为实数矩阵a，其中$a_{i,j}$代表相遇时第i条鱼吃掉第j条的概率。数据保证主对角线上只包含0，且$a_{j,i}$=$1-a_{i,j}$。每个实数小数点后只有6位。

输出格式

输出n个六位小数，以空格隔开，其中第i个表示第i条鱼存活到最后的概率。

题目描述
$ n $ fish, numbered from $ 1 $ to $ n $ , live in a lake. Every day right one pair of fish meet, and the probability of each other pair meeting is the same. If two fish with indexes i and j meet, the first will eat up the second with the probability $ a_{ij} $ , and the second will eat up the first with the probability $ a_{ji}=1-a_{ij} $ . The described process goes on until there are at least two fish in the lake. For each fish find out the probability that it will survive to be the last in the lake.

输入格式
The first line contains integer $ n $ ( $ 1<=n<=18 $ ) — the amount of fish in the lake. Then there follow $ n $ lines with $ n $ real numbers each — matrix $ a $ . $ a_{ij} $ ( $ 0<=a_{ij}<=1 $ ) — the probability that fish with index $ i $ eats up fish with index $ j $ . It’s guaranteed that the main diagonal contains zeros only, and for other elements the following is true: $ a_{ij}=1-a_{ji} $ . All real numbers are given with not more than 6 characters after the decimal point.

输出格式
Output $ n $ space-separated real numbers accurate to not less than 6 decimal places. Number with index $ i $ should be equal to the probability that fish with index $ i $ will survive to be the last in the lake.

样例 #1
样例输入 #1
1
2
3
2
0 0.5
0.5 0
样例输出 #1
1
0.500000 0.500000
样例 #2
样例输入 #2
1
2
3
4
5
6
5
0 1 1 1 1
0 0 0.5 0.5 0.5
0 0.5 0 0.5 0.5
0 0.5 0.5 0 0.5
0 0.5 0.5 0.5 0
样例输出 #2
1
1.000000 0.000000 0.000000 0.000000 0.000000

分析；

本题可以状压dp。

令 $f[S]$ 表示目前只有集合 $S$ 中的鱼活着的情况的发生概率。对于 $i ∈ [1, n]$，都应有 $∑ _{|S|=i} f[S] = 1$。

初始状态是 $f[{1,2,…,n}]=1$。

对于一个情况 $S$，我们可以直接枚举那天哪一对鱼发生了碰面，然后把这一天的概率转移到下一天上。具体地，对于一个状态 $S$，设它的大小 $|S| = m(m \ge 2)$，我们可以枚举二元组 $(i, j)$，满足 $i < j$ 且$ i, j ∈ S$，并进行转移：
$$
f[S\setminus {i}]+=\frac{f[S]}{\frac{m(m-1)}{2}}\times a_{j,i},f[s\setminus {j}]+=\frac{f[S]}{\frac{m(m-1)}{2}}\times a_{i,j}
$$
代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1<<18;

int n;
double f[N];
double a[20][20];

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> a[i][j];
        }
    }
    
    f[(1<<n)-1]=1;
    for(int i=(1<<n)-1;i>=1;i--){
        int t=__builtin_popcount(i);
        if(t==1)continue;
        for(int j=1;j<=n;j++){
            if((i&(1<<j-1))==0)continue;
            for(int k=j+1;k<=n;k++){
                if((i&(1<<k-1))==0)continue;
                double p=f[i]/(t*(t-1)/2.0);
                f[i-(1<<j-1)]+=p*a[k][j];
                f[i-(1<<k-1)]+=p*a[j][k];
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        cout << fixed << setprecision(6) << f[1<<i-1] << ' ';
    }
    return 0;
}

例题2：洛谷P5249 [LnOI2019] 加特林轮盘赌

[LnOI2019] 加特林轮盘赌
题目背景
加特林轮盘赌是一个养生游戏。

题目描述
与俄罗斯轮盘赌等手枪的赌博不同的是，加特林轮盘赌的赌具是加特林。

加特林轮盘赌的规则很简单：在加特林的部分弹夹中填充子弹。游戏的参加者坐在一个圆桌上，轮流把加特林对着自己的头，扣动扳机一秒钟。中枪的自动退出，坚持到最后的就是胜利者。

我们使用的是 2019 年最新技术的加特林，他的特点是无需预热、子弹无限，每一个人，在每一回合，中枪的概率是完全相同的 $P_0$。

每局游戏共有 $n$ 只长脖子鹿，从 1 长脖子鹿开始，按照编号顺序从小到大进行游戏，绕着圆桌不断循环。

游戏可能会循环进行多轮，直到场上仅剩下最后一只长脖子鹿时，游戏结束。

给出 $P_0$ 和 $n$，询问 $k$ 号长脖子鹿最终成为唯一幸存者的概率 $P_k$。

如果 $P_0=0$，我们认为胜者为 $1$ 号。

输入格式
仅一行三个数，$P_0,n,k$。

输出格式
一个浮点数 $P_{k}$，误差应该小于 $10^{-8}$。（请保留更多位数的小数）

样例 #1
样例输入 #1
1
0.5 2 1
样例输出 #1
1
0.33333333
样例 #2
样例输入 #2
1
0.5 2 2
样例输出 #2
1
0.66666667
样例 #3
样例输入 #3
1
0.5 3 1
样例输出 #3
1
0.23809524
样例 #4
样例输入 #4
1
0.5 3 2
样例输出 #4
1
0.28571429
提示

对于 $10%$ 的数据，$n \le 100$。

对于 $30%$ 的数据，$n \le 500$。

对于另外 $20%$ 的数据，$k = n$。

对于 $100%$ 的数据，$1 \le k \le n \le 10^{4}, 0 \le P_0 \le 1$。

所有数据的时间限制为 1000ms，空间限制为256MB，可开启 O2 优化。

前缀和优化

前缀和优化，一般用于组合计数类DP。

在DP的过程中，每次的转移对象是一段区间的求和，故可以采用前缀和来快速求和。

例题：洛谷P2513 [HAOI2009] 逆序对数列

[HAOI2009] 逆序对数列
题目描述
对于一个数列 ${a_i}$，如果有 $i<j$ 且 $a_i>a_j$，那么我们称 $a_i$ 与 $a_j$ 为一对逆序对数。若对于任意一个由 $1 \sim n$ 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 $k$ 的这样自然数数列到底有多少个？

输入格式
第一行为两个整数n，k。

输出格式
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。

样例 #1
样例输入 #1
1
4 1
样例输出 #1
1
3
提示
样例说明：

下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

测试数据范围

30%的数据 n<=12

100%的数据 n<=1000，k<=1000

分析：

考虑从小往大把1到n插入序列中。

放入元素i时，根据插入的位置可以产生$0\sim i-1$个逆序对。

用$f[i][j]$表示前i个数产生j个逆序对的方案数，转移方程为
$$
f[i][j]=\sum_{k=j-i+1}^j f[i-1][k]
$$
对$f[i][j]$记录前缀和即可$O(1)$转移。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1005,p=10000;
int n,k;
long long f[N][N];
int main(){
    cin >> n >> k;
    f[1][0]=1;
    for(int i=2;i<=n;i++){
        long long sum=0;
        for(int j=0;j<=k;j++){
            sum+=f[i-1][j];
            sum%=p;
            f[i][j]=sum;
            if(j-i+1>=0){
                sum-=f[i-1][j-i+1];
                sum%=p;
                sum+=p;
                sum%=p;
            }
        }
    }
    cout << f[n][k]%p << endl;
    return 0;
}

数据结构优化

前缀和仅适用于按照下标顺序进行转移的计数类动态规划问题。

而面对转移仍然是一个区间/矩形/树上，但是是最优化问题，或者不是按照顺序转移，则无法用前缀和优化，这个时候可以借助一些常用的数据结构，如树状数组，线段树等。

例题1：洛谷P4644 [USACO05DEC] Cleaning Shifts S

[USACO05DEC] Cleaning Shifts S
题目描述
约翰的奶牛们从小娇生惯养，她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，他不得不雇佣她们中的一些来清扫牛棚，约翰的奶牛中有 $ N(1 \leq N \leq 10000) $ 头愿意通过清扫牛棚来挣一些零花钱。

由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫。需要打扫的时段从某一天的第 $ M $ 秒开始，到第 $ E $ 秒结束 $ (0 \leq M \leq E \leq 86399) $。注意这里的秒是指时间段而不是时间点，也就是说，每天需要打扫的总时间是 $ E-M+1 $ 秒。

约翰已经从每头牛那里得到了她们愿意接受的工作计划：对于某一头牛，她每天都愿意在笫 $ T_1 \ldots T_2 $ 秒的时间段内工作 $ (M \leq T_1 \leq T_2 \leq E) $ ，所要求的报酬是 $ S $ 美元 $ (0 \leq S \leq 500000) $。与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第 $ 10 \ldots 20 $ 秒，那她总共工作的时间是 $ 11 $ 秒，而不是 $ 10 $ 秒。

约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资。现在请你帮约翰决定该雇佣哪些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小。

输入格式
第 $ 1 $ 行： $ 3 $ 个正整数 $ N,M,E $ 。

第 $ 2 $ 到 $ N+1 $ 行：第 $ i+1 $ 行给出了编号为 $ i $ 的奶牛的工作计划，即 $ 3 $ 个正整数 $ T_1,T_2,S $ 。

输出格式
输出一个整数，表示约翰需要为牛棚清理工作支付的最少费用。如果清理工作不可能完成，那么输出 $ -1 $ 。

样例 #1
样例输入 #1
1
2
3
4
3 0 4
0 2 3
3 4 2
0 0 1
样例输出 #1
1
5
提示
约翰有 $ 3 $ 头牛，牛棚在第 $ 0 $ 秒到第 $ 4 $ 秒之间需要打扫。约翰雇佣前两头牛清扫牛棚，可以只花 $ 5 $ 美元就完成一整天的清扫。

分析：

用$f[i]$表示按照从左到右的顺序选择了第$i$个区间，保证当前已经覆盖了$[L,b_i]$的所有数。

转移：
$$
f[i]=\min_{a_i<b_j<b_i}(f[j])+c_i
$$
标称了一个单点修改，区间查询最小值的问题，采用树状数组优化即可。

例题2：洛谷P3287 [SCOI2014] 方伯伯的玉米田

[SCOI2014] 方伯伯的玉米田
题目描述
方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有 $N$ 株，它们的高度参差不齐。方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间，把这个区间的玉米全部拔高 $1$ 单位高度，他可以进行最多 $K$ 次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。问能最多剩多少株玉米，来构成一排美丽的玉米。

输入格式
第一行包含两个整数 $n, K$，分别表示这排玉米的数目以及最多可进行多少次操作。第二行包含 $n$ 个整数，第 $i$ 个数表示这排玉米，从左到右第 $i$ 株玉米的高度 $a_i$。

输出格式
输出一个整数，最多剩下的玉米数。

样例 #1
样例输入 #1
1
2
3 1
2 1 3
样例输出 #1
1
3
提示
$100%$ 的数据满足：$2 \le N \lt 10^4 $，$2 \le K \le 500$，$1 \leq a_i \leq 5000$。

分析：

显然，只有每次操作都是后缀时，操作才最优。

用$F[i][j]$表示第$i$个数被进行了$j$次$+1$，以$i$结尾的最长上升子序列长度，则
$$
F[i][j]=\max_{k<i,0\le l \le j,h[i]+j \ge h[k]+l}(F[k][l])+1
$$
按照$i$的顺序，剩下的是一个二维偏序，可以用二维树状数组进行维护。

例题3：洛谷P9871 [NOIP2023] 天天爱打卡

[NOIP2023] 天天爱打卡
题目描述
小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。

开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $n$ 天，编号为从 $1$ 到 $n$。

对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $d$。初始时，他的能量值是 $0$，并且试运行期间他的能量值可以是负数。

而且大 Y 不会连续跑步打卡超过 $k$ 天；即不能存在 $1\le x\le n-k$，使得他在第 $x$ 到第 $x+k$ 天均进行了跑步打卡。

小 T 同学在软件中设计了 $m$ 个挑战，第 $i$（$1\le i \le m$）个挑战可以用三个正整数 $(x_i,y_i,v_i)$ 描述，表示如果在第 $x_i$ 天时，用户已经连续跑步打卡至少 $y_i$ 天（即第 $x_i-y_i+1$ 到第 $x_i$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $v_i$。

现在大 Y 想知道，在软件试运行的 $n$ 天结束后，他的能量值最高可以达到多少？

输入格式
本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

接下来，对于每组测试数据：

输入的第一行包含四个正整数 $n,m,k,d$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。

接下来 $m$ 行，每行包含三个正整数 $x_i,y_i,v_i$，表示一次挑战。

输出格式
输出一行一个整数表示对应的答案。

样例 #1
样例输入 #1
1
2
3
4
1 1
3 2 2 1
2 2 4
3 2 3
样例输出 #1
1
2
提示
【样例解释 #1】

在第 $1,2$ 天跑步打卡，第 $3$ 天不跑步打卡，最终会获得 $(-1)+(-1)+4=2$ 的能量值。

【样例解释 #2】

该组样例满足测试点 $3$ 的条件。

【样例解释 #3】

该组样例满足测试点 $5$ 的条件。

【样例解释 #4】

该组样例满足测试点 $15$ 的条件。

【样例解释 #5】

该组样例满足测试点 $17$ 的条件。

【样例解释 #6】

该组样例满足测试点 $19$ 的条件。

【数据范围】

记 $l_i=x_i-y_i+1$，$r_i=x_i$；

对于所有测试数据，保证：$1\le t\le 10$，$1\le k\le n\le 10^9$，$1\le m\le 10^5$，$1\le l_i\le r_i\le n$，$1\le d,v_i\le 10^9$。

测试点编号 $n \le$ $m \le$ 特殊性质

$1, 2$ $18$ $10 ^ 2$ 无

$3, 4$ $10 ^ 2$ $10 ^ 2$ 无

$5 \sim 7$ $10 ^ 3$ $10 ^ 3$ 无

$8, 9$ $10 ^ 3$ $10 ^ 5$ 无

$10, 11$ $10 ^ 5$ $10 ^ 3$ 无

$12 \sim 14$ $10 ^ 5$ $10 ^ 5$ 无

$15, 16$ $10 ^ 9$ $10 ^ 5$ A

$17, 18$ $10 ^ 9$ $10 ^ 5$ B

$19 \sim 21$ $10 ^ 9$ $10 ^ 5$ C

$22 \sim 25$ $10 ^ 9$ $10 ^ 5$ 无

特殊性质 A：$k\le 10^2$；

特殊性质 B：$\forall 1\le i<m$，$r_i<l_{i+1}$；

特殊性质 C：$\forall 1\le i<j\le m$，$l_i<l_j$，$r_i<r_j$。

测试点编号	$n \le$	$m \le$	特殊性质
$1, 2$	$18$	$10 ^ 2$	无
$3, 4$	$10 ^ 2$	$10 ^ 2$	无
$5 \sim 7$	$10 ^ 3$	$10 ^ 3$	无
$8, 9$	$10 ^ 3$	$10 ^ 5$	无
$10, 11$	$10 ^ 5$	$10 ^ 3$	无
$12 \sim 14$	$10 ^ 5$	$10 ^ 5$	无
$15, 16$	$10 ^ 9$	$10 ^ 5$	A
$17, 18$	$10 ^ 9$	$10 ^ 5$	B
$19 \sim 21$	$10 ^ 9$	$10 ^ 5$	C
$22 \sim 25$	$10 ^ 9$	$10 ^ 5$	无

分析：
因为本题要求$1$必须连续才有贡献，跨过$0$的区间没有贡献，因此可以进行如下的dp设计：

用$f_i$表示第$i$天不跑步的情况下最大贡献，注意到状态无后向性，因此从前向后处理不会产生之前的某一天对当前天有影响，因此，可以写出状态转移：
$$
f_i=\max_{i-k-1 \le j \le i-1}f_j-val(j,i)-d \times (i-j-1)
$$
其中$val(j,i)$表示$i \sim j$中如果全部跑步，能产生多少贡献，期望得分$36pts$。

注意到对于某个挑战$(l,r,w)$，如果我们在计算$f_r$后，将$l-1$以前的所有$f_i$加上$w$，就可以消除$val(i,j)$的影响，因为在之后的转移中，我们在从$f_{i-1}$及之前的位置转移时，一定会钦定$l \sim r$全部为$1$，从而产生了$w$的贡献。

对于$d \times (i-j-1)$一项，我们只需将其拆开，变为

不妨另$g_i=f_i+i \times d$，我们的转移式就变为
$$
g_i=\max_{i-k-1 \le j \le i-1}g_j-val(j,i)+d
$$

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。