飞扬的小鸟_牛客博客

定义 $dp[i][j]$ 为跳跃到 $(i,j)$ 的最小代价

那么枚举每个 $x$ 座标和每个 $y$ 座标

每个状态都是前一个位置跳跃若干次上来的,所以可以写出很暴力的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=10009;
int n,m,k,id=1;
int x[maxn],y[maxn];
struct p{
    int x,l,r;
    bool operator < (const p&tmp )    const{
        return x<tmp.x;
    }
}a[maxn];
int dp[10009][1009];
int main()
{
    cin >> n >> m >> k;
    for(int i=0;i<n;i++)    cin >> x[i] >> y[i];
    for(int i=1;i<=k;i++)
        cin >> a[i].x >> a[i].l >> a[i].r;
    sort(a+1,a+1+k);
    memset(dp,20,sizeof(dp));
    int inf=dp[0][0];
    for(int i=1;i<=m;i++)    dp[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=m;
        if( a[id].x==i )    l=a[id].l+1,r=a[id].r-1,id++;
        l = max( l,1 );
        for(int j=l;j<=r;j++)//枚举高度 
        {
            dp[i][j] = min( dp[i][j],dp[i-1][j+y[i-1]] );
            if( j==m )
            {
                for(int q=1;q<=m;q++)
                {
                    int r = (m-q)/x[i-1];    if( (m-q)%x[i-1]||q==m )    r++;
                    dp[i][j]=min( dp[i][j],dp[i-1][q]+r );
                }
                continue;
            }
            for(int q=1;j>=q*x[i-1];q++)
                dp[i][j]=min( dp[i][j],dp[i-1][j-q*x[i-1]]+q ); 
        }
    }
    int ans = inf;
    for(int i=1;i<=m;i++)
        ans = min( ans,dp[n][i] );
    if( ans==inf )
    {
        int da=0;
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=m;j++)
                if( dp[a[i].x][j]!=inf )
                {
                    da++;break;
                }
        }
        cout << 0 << endl << da;
    }
    else
        cout << 1 << endl << ans;
}

但是我们发现转移的过程非常浪费

比如 $(i,j)$ 是从 $(i-1,k)$ 跳跃若干次到达的,这样枚举复杂度太高了

$(i,j)$ 可以由 $(i,j-x[i-1])$ 转移而来,因为之前已经计算过 $(i,j-x[i-1])$

$(i,j)$ 可以由 $(i-1,j-x[i-1])$ 转移而来,就是从上一层转移过来

所以这样就优化了复杂度

#include <bits/stdc++.h>
using namespace std;
const int maxn=10009;
int n,m,k,id=1;
int x[maxn],y[maxn];
struct p{
    int x,l,r;
    bool operator < (const p&tmp )    const{
        return x<tmp.x;
    }
}a[maxn];
int dp[10009][2009];
int main()
{
    cin >> n >> m >> k;
    for(int i=0;i<n;i++)    cin >> x[i] >> y[i];
    for(int i=1;i<=k;i++)
        cin >> a[i].x >> a[i].l >> a[i].r;
    sort(a+1,a+1+k);
    memset(dp,20,sizeof(dp));
    int inf=dp[0][0];
    for(int i=1;i<=m;i++)    dp[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=m;
        if( a[id].x==i )    l=a[id].l+1,r=a[id].r-1,id++;
        l = max( l,1 );
        for(int j=1;j<=r;j++)
        {
            if( j==m )    continue;
            if( j-x[i-1]>=1 )    
            dp[i][j]=min( dp[i][j],min( dp[i-1][j-x[i-1]],dp[i][j-x[i-1]])+1 );
        }
        if( r>=m )
        {
            for(int j=m-x[i-1];j<=m;j++)
            if( j>=1 )    dp[i][m]=min( dp[i][m],min( dp[i-1][j],dp[i][j])+1 );
        }
        for(int j=l;j<=r;j++)
            dp[i][j] = min(dp[i][j],dp[i-1][j+y[i-1]]); 
        for(int j=1;j<=l-1;j++)    dp[i][j]=inf;
    }
    int ans = inf;
    for(int i=1;i<=m;i++)
        ans = min( ans,dp[n][i] );
    if( ans==inf )
    {
        int da=0;
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=m;j++)
                if( dp[a[i].x][j]!=inf )
                {
                    da++;break;
                }
        }
        cout << 0 << endl << da;
    }
    else
        cout << 1 << endl << ans;
}