题解：P1478 陶陶摘苹果（升级版）

Backpack_dp · 2026-01-21 00:17:49 · 题解

观察到这题很明显是一个背包。

但使用 TiJie 思想发现本题可以用贪心，由于贪心我不太会（其实本来就没想到用贪心），于是使用背包来做此题。

我们将每个苹果看作物品，力气 s 看作背包容量。就不难看出本题是一个很板子的 01 背包。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define F(a,b) for(int i=(a);i<=(b);i++)
#define f(a,b) for(int j=(a);j>=(b);j--)
#define N 5050
int n,s,a,b,x[N],y[N],dp[1010];
signed main(){
    cin>>n>>s;
    cin>>a>>b;
    F(1,n){
        cin>>x[i]>>y[i];
        x[i]-=a;
    }
    F(1,n){
        f(s,y[i]){
            if(x[i]<=b){
                dp[j]=max(dp[j],dp[j-y[i]]+1);
            }
        }
    }
    cout<<dp[s];
    return 0;
}

//gugugaga

虽然不是最优解，但我们仍旧可以尝试优化其时间：

• 可以在输入时将无法够到的苹果直接舍弃，即不进入 x，y 数组。
• 不使用 max 使用三目运算符等。

优化后的代码就不放了，可以自己尝试一下。

以上就是本题解的全部内容，谢谢观看。