Miku

定义$f_{i j}$为到达（i,j）的最小代价

然后对于从下往上，因为可以点无数次，是个完全背包，从上往下就一次，01背包，飞到天花板上的，拽下来

水管特判

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10005;
int n,m,k;
int x[maxn],y[maxn];
int l[maxn],h[maxn];
int f[maxn];
int dp[maxn][2005];
int p,a,b;
int ans=1061109567;
int main(){
    memset(dp,0x3f,sizeof(dp));
//  cout<<0x3f3f3f3f3f;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x[i],&y[i]);
        l[i]=0;
        h[i]=m+1;
    }
    for(int i=1;i<=k;++i){
        scanf("%d",&p);
        scanf("%d%d",&l[p],&h[p]);
        f[p]=1;
    }
    for(int i=1;i<=m;++i){
        dp[0][i]=0;
    }
    for(int i=1;i<=n;++i){
        for(int j=x[i]+1;j<=x[i]+m;++j){
            dp[i][j]=min(dp[i-1][j-x[i]],dp[i][j-x[i]])+1;
        }
        for(int j=m+1;j<=m+x[i];++j){
            dp[i][m]=min(dp[i][m],dp[i][j]);
        }
        for(int j=m-y[i];j;--j){
            dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);
        }
        for(int j=1;j<=l[i];++j){
            dp[i][j]=1061109567;
        }
        for(int j=h[i];j<=m;++j){
            dp[i][j]=1061109567;
        }
    }
    for(int i=1;i<=m;++i){
        ans=min(ans,dp[n][i]);
    }
    if(ans<1061109567){
        cout<<1<<endl;
        cout<<ans;
//      cout<<423;
    }else{
        ans=0;
        cout<<0<<endl;
        for(int i=n;i;--i)
            for(int j=1;j<=m;++j){
                if(dp[i][j]<1061109567){
                    for(int z=1;z<=i;++z){
                        ans+=f[z];
                    }
                    cout<<ans;
                    return 0;
                }
            }
    }
    return 0;
}