$O(nm^2)$

状态定义:$f[i][j]$ 表示走到$i$,高度为$j$的最小值

状态计算:

不按:$f[i][j]=f[i-1][j+y[i]]$

按:$f[i][j]=min(f[i][j-k*x[i]]+k)$

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=1010,INF=0x3f3f3f3f;
int n,m,k;
int x[N],y[N];//每个位置上升和下降的高度
int l[N],h[N];//管子的上下坐标
int f[N][M];//f[i][j]表示走到第i个位置高度为j的最少步数
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];//对应的位置变化
    }
    while(k--)
    {
        int p,a,b;
        cin>>p>>a>>b;
        l[p]=a,h[p]=b; //记录p这个位置对应的管子
    }
    memset(f,0x3f,sizeof f);//初始化
    for(int i=1;i<=m;i++)
    {
        f[0][i]=0;//起点位置都可以
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(!h[i]||j>l[i]&&j<h[i]) //当前高度合法
            {
                f[i][j]=f[i-1][j+y[i]];//直接掉落
                for(int k=1;k*x[i]<j;k++) //枚举按的次数
                {
                    f[i][j]=min(f[i][j],f[i-1][j-k*x[i]]+k);
                }
            }
        }
        if(!h[i]) //当前没有管子,处理高度为m的状态
        {
            f[i][m]=f[i-1][m]+1;
            //f[i][m]=min(f[i][m],f[i-1][m]+1);//点击一下
            for(int j=1;j<m;j++) //从j到m需要按几次
            {
                f[i][m]=min(f[i][m],f[i-1][j]+(m-j+x[i]-1)/x[i]);
            }
        }
    }
    int res=INF;
    for(int i=1;i<=m;i++) //枚举距离为i的每个高度
    {
        res=min(res,f[n][i]);
    }
    if(res<INF)
    {
        puts("1");
        cout<<res<<endl;
    }
    else
    {
        puts("0");
        for(int i=n;i>=0;i--) //从后往前去找到可以走到的位置
        {
            for(int j=1;j<=m;j++)
            {
                if(f[i][j]<INF)
                {
                    int cnt=0;
                    for(int k=0;k<=i;k++) //从起点到当前位置的管子数目
                    {
                        if(h[k])
                        {
                            cnt++;
                        }
                    }
                    cout<<cnt<<endl;
                    return 0;
                }
            }
        }
    }
    return 0;
}

$O(nm)$

可以使用一个g数组去储存重复选的时候枚举的最小值

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=1010,INF=0x3f3f3f3f;
int n,m,k;
int x[N],y[N];
int l[N],h[N];
int f[N][M],g[N][M];
//f[i][j]表示走了距离i到高度j的最小操作次数
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    while(k--)
    {
        int p,a,b;
        cin>>p>>a>>b;
        l[p]=a,h[p]=b;
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=m;i++)
    {
        f[0][i]=0;
    } 
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++)
    {
       
        for(int j=1;j<m;j++)
        {
            if(j>x[i])
            {
                g[i][j]=min(g[i][j-x[i]]+1,f[i-1][j-x[i]]+1);
            }
            if(!h[i]||j>l[i]&&j<h[i]) //没有管子或者是在管子范围内
            {
                f[i][j]=g[i][j];
                if(j+y[i]<=m) //不点击
                {
                    f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
                }
            }
        }
        if(!h[i])
        {
            f[i][m]=min(f[i][m],f[i-1][m]+1);//点击一下
            for(int j=1;j<m;j++)
            {
                f[i][m]=min(f[i][m],f[i-1][j]+(m-j+x[i]-1)/x[i]);//从j点击对应次数到m
            }
        }
    }
    int res=INF;
    for(int i=1;i<=m;i++) //枚举到达的高度
    {
        res=min(res,f[n][i]);
    }
    if(res<INF)
    {
        puts("1");
        cout<<res<<endl;
    }
    else
    {
        puts("0");
        for(int i=n;i>=0;i--)
        {
            bool flag=false;
            for(int j=1;j<=m;j++)
            {
                if(f[i][j]<INF)
                {
                    int cnt=0;
                    for(int k=0;k<=i;k++)
                    {
                        if(h[k])
                        {
                            cnt++;
                        }
                    }
                    cout<<cnt<<endl;
                    flag=true;
                    return 0;
                }
            }
        }
    }
    return 0;
}