若不说明，下标中的数均为整数。

1.线性DP

A.[POI2013] BAJ-Bytecomputer

给定一个长度为 $n$ 的只包含 $-1,0,1$ 的数列 $a$，每次操作可以使 $a_i\gets a_i+a_{i-1}$，求最少操作次数使得序列单调不降。如果不可能通过该操作使得序列单调不降，请输出 BRAK。

数据范围：$1\le n\le 10^6$。

引理：如果要求操作最少，则该数列中只有$1,0,-1$三种值。

证明：若不然，设最终序列中的第一个比$-1$小的数为$a_{i}$，注意到$i>1$，且$a_{i-1}\leq -1$，这与单调不降矛盾，比1大的情形可以类似地证明。$\square$

从而该数组每个操作后的数可以唯一确定，并且若操作的数前的数列单调不降，要使包括该数在内的数列单调不降，只需要操作该数。该问题具有最优子结构且易于定态，可以考虑DP处理。设$dp[i][j]$为在前$i$个数为单调不降且第$i$个数为$j$的最小操作数，容易知道$dp[1][a[1]] = 0$，并将其余状态初始化为$+\infty$，对$a[i]$、$j$分情况讨论：

若$a[i]=-1$

1.$j=-1$，则$a_{i-1}$只能是$-1$，即

\[ dp[i][-1]=dp[i-1][-1] \tag{1} \]

2.$j=0$，容易知道无论前一个数是多少都无法转移。

3.$j=1$,则$a_{i-1}$可以任取，但不能从$0,-1$转移得到，即

\[ dp[i][1] = dp[i-1][1]+2 \tag{2} \]

若$a[i]=0$

1.$j=-1$，则$a_{i-1}$只能是$-1$，即

\[ dp[i][-1]=dp[i-1][-1] + 1 \tag{3} \]

2.$j=0$，则前一个数可以是$-1,0$，即

\[ dp[i][0]=\min(dp[i-1][-1],dp[i-1][0]) \tag{4} \]

3.$j=1$,则$a_{i-1}$可以任取，但不能从$0,-1$转移得到，即

\[ dp[i][1] = dp[i-1][1]+1 \tag{5} \]

若$a[i]=1$

1.$j=-1$，则$a_{i-1}$不能取$1，0$，即

\[ dp[i][-1]=dp[i-1][-1]+2\tag{6} \]

2.$j=0$，则$a_{i-1}$不能取$1，0$，即

\[ dp[i][0]=dp[i-1][-1]+1\tag{7} \]

3.$j=1$,则$a_{i-1}$可以任取，即

\[ dp[i][1]=\min(dp[i-1][-1],dp[i-1][0],dp[i-1][1]) \tag{8} \]

综合上述八式，优化下标，查询$\max(dp[n][0],dp[n][1],dp[n][-1])$，若为$+\infty$则无解，否则输出答案。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

const int N = 0x7fffff;
int n;
int a1[N];
int dp[N][7];
//2=-1,3=0,4=1;
int main() {
    cin >> n;
    a1[0] = 0;
    for (int i = 1; i <= 1000500; i++) {
        for (int j = 0; j < 7; j++)
            dp[i][j] = N;
    }
    for (int i = 1; i <= n; i++) { cin >> a1[i]; }
    int p = a1[1];
    dp[1][p + 3] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i][2] = dp[i - 1][2] + a1[i] + 1;
        if (a1[i] == 0)dp[i][3] = min(dp[i - 1][2], dp[i - 1][3]);
        else if (a1[i] == 1) dp[i][3] = dp[i - 1][2] + 1;
        if (a1[i] == 1) dp[i][4] = min(min(dp[i - 1][2], dp[i - 1][3]), dp[i - 1][4]);
        else dp[i][4] = dp[i - 1][4] - a1[i] + 1;
    }
    if (dp[n][2] >= N && dp[n][3] >= N && dp[n][4] >= N) {
        cout << "BRAK";
        return 0;
    }
    else {
        cout << min(min(dp[n][3], dp[n][2]), dp[n][4]);
        return 0;
    }
}

B.[SCOI2009] 粉刷匠

windy 有 $N$ 条木板需要被粉刷。每条木板被分为 $M$ 个格子。每个格子要被刷成红色或蓝色。

windy 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。

如果 windy 只能粉刷 $T$ 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

数据范围：$1 \le N,M \le 50,0 \le T \le 2500$

将每条木板看作一组物品，则题目变为分组背包。那么问题落到了如何求这一组物品的每个次数的最多正确粉刷数上。

考虑如何定态，首先要有涂了$k$次作为状态，此外还要有前$j$个为最小作为递推依据，用$i$来表示是第几条木板。在每次状态转移时，需要遍历前面所有$k$到$j$的少涂一次的状态（这是因为不可能有比$k$小的区间涂了k次），并加上从$q$到$j$的最多的颜色即可，即：

\[ dp1[i][j][k]=\max(dp1[i][q][k - 1] + \max(a[i][j] - a[i][q], j - q - (a[i][j] - a[i][q])))(q\in(k,j)) \tag{1} \]

其中$a[i][j]$为用0-1前缀和来存每个区间内的颜色个数。初态为$dp1[i][j][k]=0$。

注意：应先循环涂的次数再循环涂了第几个，这与区间DP先循环区间长度再循环从第几个开始涂相似，都是用次数作为每一维的递推依据，再在这一维做第几个的递推。

从而$dp[i][m][k]$即为这一条木板粉刷次数为$k$时的最多粉刷格。

最后，进行分类背包dp即可。

\[ dp[j] = \max(dp[j - k] + dp1[i][m][k])(k\in[0,m],i\in[1,n]) \tag{2} \]

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;

const int N = 0x7ffff;
int n, m, t;
int a[100][100];
int duan[N];
int dp[1001];
int sum[101][101][101];
int main() {
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char p;
            cin >> p;
            if (p == '1')a[i][j] = 1 + a[i][j - 1];
            else a[i][j] = a[i][j - 1];
        }
    }
    //要sum[i][m][j]
    memset(sum, 0, sizeof(sum));
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {//涂了几次
            for (int j = 1; j <= m; j++) {//这一行第几个
                for (int q = k - 1; q < j; q++) {//遍历前几个少涂一次的情况
                    sum[i][j][k] = max(sum[i][q][k - 1] + max(a[i][j] - a[i][q], j - q - (a[i][j] - a[i][q])), sum[i][j][k]);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = t; j >= 1; j--) {
            for (int k = 1; k <= j; k++) {
                dp[j] = max(dp[j - k] + sum[i][m][k], dp[j]);
            }
        }
    }
    cout << dp[t];
}

C.饥饿的奶牛

有 $N$ 个区间，每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。

求出最多能吃到的牧草堆数。

数据范围：$1 \leq n \leq 1.5 \times 10^5$，$0 \leq x \leq y \leq 3 \times 10^6$。

先对每个区间按照$x$进行排序。

设$dp[i]$为区间$[1,i]$上能吃到的最多牧草。似乎如果用dp，时间复杂度$O(n^{2})$不可行，但我们可以进行双指针优化，对已经循环到的区间左端，遍历左端点相同的区间，更新每个左端点相同的区间的右端的值为选与不选改区间中的最大值，即：

\[ dp[a[p].r]=\max(dp[a[p].r],dp[a[p].l-1]+a[p].r-a[p].l+1) (p\in[1,n]) \tag{1} \]

其中

\[ a[p].l=i \tag{2} \]

对于$i$而言，将其从1遍历到$max(a[n].r)$，由于不确定是不是某个区间的端点值，则直接与上一个值传递即可，若是端点值其转移已经在$(1)$中体现，即：

\[ dp[i]=\max(dp[i-1],dp[i]) \tag{3} \]

总而言之，i的遍历是为了保证动态转移的连续，而p的遍历是为了算出特别点的转移。

最后，在每次转移记录一次值更新答案即可。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =0x7fffff;
struct len{
    long long l = 0,r = 0;
}a[N];
long long dp[N];
bool cmp(len a,len b){
    if(a.l == b.l) return a.r<b.r;
    return a.l<b.l;
}

int main(){
    int n;cin>>n;
    long long maxy;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        maxy = max(maxy,a[i].r);
    }
    sort(a+1,a+n+1,cmp);
    int p = 1;
    long long ans =0;
    for(int i=0;i<=maxy;i++){
        dp[i]=max(dp[i],dp[i-1]);
        while(a[p].l == i && p<=n){//找左端点相同的
            dp[a[p].r]=max(dp[a[p].r],dp[a[p].l-1]+a[p].r-a[p].l+1);//a[p].l-1是正好贴着a[p]的
            p++;
        }
        ans = max(ans,dp[i]);
    }
    cout<<ans;
}

2.记忆化搜索

A.[NOIP2010 提高组] 乌龟棋

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

数据范围： $1≤N≤350,1≤M≤120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。

一道经典的记忆化搜索。用$dp[i][j][k][l]$表示用了$i$张一步卡，$j$张两步卡，$k$张三步卡，$l$张四步卡的最大分数，则有

\[ dp[c1][c2][c3][c4] = \max(dp[c1-1][c2][c3][c4],dp[c1][c2-1][c3][c4],dp[c1][c2][c3-1][c4],dp[c1][c2][c3][c4-1])+a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1] \]

其中$a[i]$为该位置的分数，初态为$dp[0][0][0][0]=a[1]$，其余赋值为$-1$。

按照上式dfs+剪枝即可。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 0x7fffff;
int n, m;
int p[5];
int a[400];
int dp[40][40][40][40];


int dfs(int c1, int c2, int c3, int c4) {
    int t1 = -1, t2 = -1, t3 = -1, t4 = -1;

    if (c1 != 0) {
        if (dp[c1 - 1][c2][c3][c4] != -1) t1 = dp[c1 - 1][c2][c3][c4] + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
        else t1 = dfs(c1 - 1, c2, c3, c4) + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
    }

    if (c2 != 0) {
        if (dp[c1][c2 - 1][c3][c4] != -1) t2 = dp[c1][c2 - 1][c3][c4] + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
        else t2 = dfs(c1, c2 - 1, c3, c4) + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
    }

    if (c3 != 0) {
        if (dp[c1][c2][c3 - 1][c4] != -1) t3 = dp[c1][c2][c3 - 1][c4] + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
        else t3 = dfs(c1, c2, c3 - 1, c4) + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
    }

    if (c4 != 0) {
        if (dp[c1][c2][c3][c4 - 1] != -1) t4 = dp[c1][c2][c3][c4 - 1] + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
        else t4 = dfs(c1, c2, c3, c4 - 1) + a[c1 + 2 * c2 + 3 * c3 + 4 * c4 + 1];
    }

    dp[c1][c2][c3][c4] = max(t1, max(t2, max(t3, t4)));

    return max(t1, max(t2, max(t3, t4)));
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int x; cin >> x;
        p[x]++;
    }
    for (int i = 0; i <= 39; i++)
        for (int j = 0; j < 40; j++)
            for (int k = 0; k < 40; k++)
                for (int l = 0; l < 40; l++)
                    dp[i][j][k][l] = -1;
    dp[0][0][0][0] = a[1];
    int ans = dfs(p[1], p[2], p[3], p[4]);
    cout << ans;
}

3.区间DP

A.[CQOI2007] 涂色

假设你有一条长度为 $5$ 的木板，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：$ $ 。

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 $\texttt{RRRRR}$ ，第二次涂成 $\texttt{RGGGR}$ ，第三次涂成 $\texttt{RGBGR}$ ，达到目标。

用尽量少的涂色次数达到目标。

数据范围： $1\le n\le 50$ 。

裸的区间dp。方程：

\[ dp[j][i + j] = min(dp[j][i + j], dp[j][j + k] + dp[j + k + 1][j + i] - (a[j] == a[j + i]))(i\in[2,n-1],j\in[1,n-i],k\in[0,i]) \]

其中$a[i]$ 为字符串的第$i$ 个字符，初态为$dp[n][n] =1$，同时初始化含两个字符的区间。

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 0x7fff;
int a[N];
int dp[100][100];
char x[60];
int main() {
    cin >> x; int n = 0;
    while (x[n] >= 65) {
        a[n + 1] = x[n];
        n++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = 1000;
    for (int i = 1; i < n; i++) {
        dp[i][i] = 1;
        if (a[i] == a[i + 1]) dp[i][i + 1] = 1;
        else dp[i][i + 1] = 2;
    }
    dp[n][n] = 1;
    for (int i = 2; i < n; i++) {//长度
        for (int j = 1; j + i <= n; j++) {//起点
            for (int k = 0; k < i; k++) {
                if (a[j] == a[j + i]) dp[j][i + j] = min(dp[j][i + j], dp[j][j + k] + dp[j + k + 1][j + i] - 1);
                else dp[j][i + j] = min(dp[j][i + j], dp[j][j + k] + dp[j + k + 1][j + i]);
            }
        }
    }
    cout << dp[1][n];
}

4.背包DP

A.[BJOI2019] 排兵布阵

小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。

如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。

现在小 C 即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 $s$ 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一，你只需要输出小 C 总分的最大值。

数据范围： $1\le s \le 100$ $1\le n \le 100$ $1\le m \le 20000$ 对于每名玩家 $a_i \ge 0$，$\sum\limits_{i=1}^n a_i \le m$

分组背包裸题，方程：

\[ dp[i][j] = \max(dp[i - 1][j],dp[i - 1][j - 2 * a[i].zu[k] - 1] + i * k) (i\in[1,n],j\in[1,m],k\in[1,s]) \]

细节：每个组要先排序，严格大于意味着花费是两倍还要再加一。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 0x7fffff;
int n,m,s;
struct p
{
    int hang;
    int zu[120];
}a[120];

int b[105][105];

int dp[10001][10001];
int main(){
    cin>>s>>n>>m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= s;j++){
            int x;cin>>x;
            b[i][j] = x;
        }
    }
    for(int j = 1;j <= s;j++){
        for(int i = 1;i <= n;i++){
            a[i].zu[j] = b[i][j];
        }
        sort(a[j].zu + 1,a[j].zu + s + 1);
    }
    for(int i = 1;i <= n;i++){
        for(int j = m;j >= 1;j--){
            for(int k = 1;k <= s;k++){
                if(j > 2 * a[i].zu[k]) dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 2 * a[i].zu[k] - 1] + i * k);
            }
        }
    }
    cout<<dp[n][s];
}

B.垃圾陷阱

卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方，它的深度为 $D$（$2 \le D \le 100$）英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间 $t$（$1 \le t \le 1000$），以及每个垃圾堆放的高度 $h$（$1 \le h \le 25$）和吃进该垃圾能维持生命的时间 $f$（$1 \le f \le 30$），要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续 $10$ 小时的能量，如果卡门 $10$ 小时内（不含 $10$ 小时，维持生命的时间同）没有进食，卡门就将饿死。

第一行为两个整数，$D$ 和 $G$（$1 \le G \le 100$），$G$ 为被投入井的垃圾的数量。

第二到第 $G+1$ 行每行包括三个整数：$T$（$1 \le T \le 1000$），表示垃圾被投进井中的时间；$F$（$1 \le F \le 30$），表示该垃圾能维持卡门生命的时间；和 $H$（$1 \le H \le 25$），该垃圾能垫高的高度。

将$D$看作背包容量，用该高度与时间的最大体力当作状态，则题目变为在限制条件求下最快填满背包的时间，吃掉用刷表法，垫起来用填表法（这是因为填表不好初始化，且不好与吃掉同步）。吃掉的方程：

\[ dp[i][j] = \max(dp[i - 1][j] + n[i].f - n[i].t + n[i-1].t) \tag{1} \]

垫起来的方程：

\[ dp[i][j + n[i].h] = \max(dp[i][j + n[i].h],dp[i - 1][j] - n[i].t + n[i-1].t) \tag{2} \]

转移条件：

\[ dp[i - 1][j] \ge n[i].t - n[i-1].t \tag{3} \]

其中$n[i]$为对$t$排序后的第$i$物品。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 0x7fffff;
int d,g;
struct node
{
    int t,f,h;
}n[10000];
bool cmp(node a,node b){
    return a.t<b.t;
}
int dp[150][150];

int main(){
    cin>>d>>g;
    for(int i=1;i<=g;i++){
        cin>>n[i].t>>n[i].f>>n[i].h;
    }
    sort(n+1,n+g+1,cmp);
    dp[0][0] = 10;
    memset(dp,-100,sizeof(dp));
    dp[0][0] = 10;
    int ans = -100000;
    for(int i = 1;i<=g;i++){
        for(int j = d; j >= 0;j--){
            if(dp[i - 1][j] < n[i].t - n[i-1].t) continue;
            if(j + n[i].h >= d){
                cout<<n[i].t;
                return 0;
            }
            dp[i][j] = max(dp[i][j],dp[i - 1][j] + n[i].f - n[i].t + n[i-1].t);//吃掉
            dp[i][j + n[i].h] = max(dp[i][j + n[i].h],dp[i - 1][j] - n[i].t + n[i-1].t);//垫起来
        }
        ans = max(ans,n[i].t + dp[i][0]);
    }//体力一定要最多
    cout<<ans;
}

C.[NOIP2014 提高组] 飞扬的小鸟

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 $n$，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 $1$，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 $x$，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 $y$。小鸟位于横坐标方向不同位置时，上升的高度 $x$ 和下降的高度 $y$ 可能互不相同。

小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

第 $1$ 行有 $3$ 个整数 $n, m, k$，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 $n$ 行，每行 $2$ 个用一个空格隔开的整数 $x$ 和 $y$，依次表示在横坐标位置 $0 \sim n-1$ 上玩家点击屏幕后，小鸟在下一位置上升的高度 $x$，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 $y$。

接下来 $k$ 行，每行 $3$ 个整数 $p,l,h$，每两个整数之间用一个空格隔开。每行表示一个管道，其中 $p$ 表示管道的横坐标，$l$ 表示此管道缝隙的下边沿高度，$h$ 表示管道缝隙上边沿的高度（输入数据保证 $p$ 各不相同，但不保证按照大小顺序给出）。

对于 $100\%$ 的数据：$5 \leq n \leq 10000$，$5 \leq m \leq 1000$，$0 \leq k < n$，$0 < x,y < m$，$0 < p < n$，$0 \leq l < h \leq m$， $l + 1 < h$。

建模为两个背包：上升为完全背包，下降为01背包。

对于下降而言没什么坑点，但对于上升而言，必须特判到最顶点的情况，以及特判在初始时刻能从原点出发。

最后还要注意排序也有坑点。

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 0x7fffff;
int n, m, k;
struct guan
{
    int maxh, minh, x = 0x7ff;
} n1[10500];
struct updown
{
    int up, down;
} move1[10500];
int ha[10500];
int dp[10500][1050];
bool cmp(guan a, guan b)
{
    return a.x < b.x ? 1 : 0;
}
int new_h[10500][1050];

int main()
{
    cin >> n >> m >> k;
    int cnt1 = 1;
    memset(ha, 0, sizeof(ha));
    for (int i = 0; i < n; i++)
        cin >> move1[i].up >> move1[i].down;
    for (int i = 1; i <= k; i++)
    {
        int x;
        cin >> x;
        ha[x]++;
        cin >> n1[i].minh >> n1[i].maxh;
        n1[i].x = x;
        cnt1++;
    }
    sort(n1 + 1, n1 + k + 1, cmp);
    memset(dp, 0x3f, sizeof(dp));
    int cnt2 = 1;
    for (int i = 1; i <= m; i++)
    {
        dp[0][i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        new_h[i][1] = move1[i].up;
        int cnt = 2;
        for (int j = 2; j * move1[i].up <= m; j++)
        {
            new_h[i][cnt++] = j * move1[i].up;
        }
        new_h[i][cnt] = -1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!ha[i])
        {
            if (i == 1)
                for (int j = 0; j <= m; j++)
                {
                    if (j >= move1[i - 1].up)
                    {
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - move1[i - 1].up] + 1);
                        dp[i][j] = min(dp[i][j], dp[i][j - move1[i - 1].up] + 1);
                    }
                }
            else
                for (int j = 1; j <= m; j++)
                {
                    if (j >= move1[i - 1].up)
                    {
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - move1[i - 1].up] + 1);
                        dp[i][j] = min(dp[i][j], dp[i][j - move1[i - 1].up] + 1);
                    }
                }
            if (i == 1)
                for (int j = 0; j <= m; j++)
                {
                    if (j + move1[i - 1].down <= m)
                        dp[i][j] = min(dp[i][j], dp[i - 1][j + move1[i - 1].down]);
                }
            else
                for (int j = 1; j <= m; j++)
                {
                    if (j + move1[i - 1].down <= m)
                        dp[i][j] = min(dp[i][j], dp[i - 1][j + move1[i - 1].down]);
                }
            for (int j = m - move1[i - 1].up; j <= m; j++)
            {
			    dp[i][m]=min(dp[i][m],min(dp[i][j],dp[i-1][j])+1);
            }
            dp[i][m] = min(dp[i - 1][m] + 1, dp[i][m]);
        }
        if (ha[i])
        {
            if (i == 1)
                for (int j = 0; j <= m; j++)
                {
                    if (j >= move1[i - 1].up)
                    {
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - move1[i - 1].up] + 1);
                        dp[i][j] = min(dp[i][j], dp[i][j - move1[i - 1].up] + 1);
                    }
                }
            else
                for (int j = 1; j <= m; j++)
                {
                    if (j >= move1[i - 1].up)
                    {
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - move1[i - 1].up] + 1);
                        dp[i][j] = min(dp[i][j], dp[i][j - move1[i - 1].up] + 1);
                    }
                }
            if (i == 1)
                for (int j = 0; j <= m; j++)
                {
                    if (j + move1[i - 1].down <= m)
                        dp[i][j] = min(dp[i][j], dp[i - 1][j + move1[i - 1].down]);
                }
            else
                for (int j = 1; j <= m; j++)
                {
                    if (j + move1[i - 1].down <= m)
                        dp[i][j] = min(dp[i][j], dp[i - 1][j + move1[i - 1].down]);
                }
            for (int j = m - move1[i - 1].up; j <= m; j++)
            {
			    dp[i][m]=min(dp[i][m],min(dp[i][j],dp[i-1][j])+1);
            }
            dp[i][m] = min(dp[i - 1][m] + 1, dp[i][m]);
            int res = 0x3f3f3f3f;
            for (int j = n1[cnt2].minh + 1; j <= n1[cnt2].maxh - 1; j++)
            {
                res = min(res, dp[i][j]);
            }
            for (int j = 1; j <= m; j++)
            {
                if (!(j >= n1[cnt2].minh + 1 && j <= n1[cnt2].maxh - 1))
                    dp[i][j] = 0x3f3f3f3f;
            }
            if (res >= 0x3f3f3f3f)
            {
                cout << 0 << endl
                     << cnt2 - 1;
                return 0;
            }
            cnt2++;
        }
    }
    int ans = 0x7ffff;
    for (int i = 1; i <= m; i++)
        ans = min(ans, dp[n][i]);
    cout << 1 << endl
         << ans << endl;
    return 0;
}