#include <bits/stdc++.h>

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

const int N=10024;
const int M=1024;

int n,m,k;
int x[N],y[N],l[N],h[N];
int mem[N][M][2],vis[N][M][2];

int dp(int i,int j,bool u) // 宽度为 i，高度为 j 时，u 表示此宽度时，是否（1/0）上升过？
{
    if(i==n+1) return 0;
    int& ans=mem[i][j][u];
    if(j>=l[i]&&j<=h[i]) return 1<<20; // 不允许触摸到禁封范围
    if(vis[i][j][u]) return ans;
    vis[i][j][u]=1;
    ans=1<<20;
    // u 的作用是区分决策类型
    // 决策 1：上升
    // 第一种情况，运用背包的思想，不停地往上升，但宽度不变
    if(j<m) ans=min(ans,1+dp(i,min(j+x[i],m),1));
    // 第二种情况，不升了，结束决策 1
    if(u==1) ans=min(ans,dp(i+1,j,0));
    // 决策 2: 下降
    if(u==0) ans=min(ans,dp(i+1,max(j-y[i],0),0));
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m>>k;
    vector<int> f(n+1,0);
    rep(i,1,n) cin>>x[i]>>y[i]; // 上升权值，下降全职
    rep(i,1,k)
    {
        int p; cin>>p; p++;
        cin>>l[p]>>h[p];
        f[p]=1;
        // 被禁止的高度
    }
    int ans=1<<20;
    rep(i,1,m) // 枚举初始高度
        ans=min(ans,dp(1,i,0));
    if(ans>=(1<<20))
    {
        int cnt=0;
        rep(i,1,n)
        {
            int fg=0;
            rep(j,1,m) if(dp(i,j,0)<(1<<20)||dp(i,j,1)<(1<<20)) fg=1;
            if(fg&&f[i]) cnt++;
        }
        cout<<0<<endl<<cnt<<endl;
    }
    else cout<<1<<endl<<ans<<endl;
}

求解：样例没过，但有 30 pts。

采用的是记忆化搜索，思路和所有题解不同！

玄 关。