分析

首先我们可以列出一个转移方程式

我们发现这个转移式其实是
01背包和完全背包的合并版
所以我们可以分开进行维护
温馨提示:一定要理清思路之后再下手,不然就
在线%JK_LOVER巨佬

代码

//P1941
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f
#define Mod 998244353
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=1e4+10,MaxM=1e3+10;

int DP[MaxN][MaxM];
int Row,Line,Total;
int u,v,w,Opt,Top[MaxN],Low[MaxN];
int X[MaxN],Y[MaxN],E[MaxN];
bool Jud[MaxN];
struct Node {
    int Loc,L,R;
    friend bool operator < (Node A,Node B)
    { return A.Loc<B.Loc; }
}Num[MaxN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Solve() {
    FOR(i,1,Line) {
        int Jud=i,Opt=i-1;
        Cl(DP[i],0x3f);
        FOR(j,X[i]+1,Row+X[i]) { DP[Jud][j]=min(DP[Opt][j-X[i]]+1,DP[Jud][j-X[i]]+1); } 
        FOR(j,Row+1,Row+X[i]) { DP[Jud][Row]=min(DP[Jud][Row],DP[Jud][j]); }
        FOR(j,1,Row-Y[i]) { DP[Jud][j]=min(DP[Jud][j],DP[Opt][j+Y[i]]); }
        FOR(j,1,Low[i]-1) { DP[Jud][j]=INF; }
        FOR(j,Top[i]+1,Row) { DP[Jud][j]=INF; }
    }
    // Cl(DP[0],0);
    // FOR(i,1,Line) {
    //     int Jud=(i & 1);
    //     int Opt=(Jud ^ 1);
    //     Cl(DP[Jud],0x3f);
    //     int A=max(Low[i],Low[i-1]+X[i-1]),B=min(Top[i],Top[i-1]+X[i-1]);
    //     FOR(j,max(Low[i],Low[i-1]+X[i-1]),min(Top[i],Top[i-1]+X[i-1])) DP[Jud][j]=min(DP[Jud][j],DP[Opt][j-X[i-1]]+1);
    //     FOR(j,max(Low[i],Low[i-1]-Y[i-1]),min(Top[i],Top[i-1]-Y[i-1])) DP[Jud][j]=min(DP[Jud][j],DP[Opt][j+Y[i-1]]);
    //     if(A>B) { FOR(j,1,Row) DP[Jud][Row]=min(DP[Opt][j]+1,DP[Jud][Row]); }
    //     FOR(j,1,Row) { cout<<"i: "<<i<<" j: "<<j<<" DP: "<<DP[Jud][j]<<endl; }
    // }
}

int main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Line>>Row>>Total;
    FOR(i,1,Line) { cin>>X[i]>>Y[i]; }
    FOR(i,1,Total) { cin>>Num[i].Loc>>Num[i].L>>Num[i].R; E[Num[i].Loc]=i; }
    FOR(i,0,Line) {
        if(E[i]) { Low[i]=Num[E[i]].L+1; Top[i]=Num[E[i]].R-1; Jud[i]=true; }
        else { Low[i]=1; Top[i]=Row; }
        // cout<<"Low: "<<Low[i]<<" Top: "<<Top[i]<<endl;
    }
    Solve();
    int Ans=INF;
    FOR(i,1,Row) { Ans=min(Ans,DP[Line][i]); }
    if(Ans<INF) { cout<<"1"<<endl<<Ans<<endl; }
    else {
        int i,j;
        for(i=Line;i>=1;i--) { for(j=1;j<=Row;j++) { if(DP[i][j]<INF) { break; } } if(j<=Row) break; }
        Ans=0;
        FOR(j,1,i) { if(Jud[j]) Ans++; }
        cout<<"0"<<endl<<Ans<<endl;
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}