题目P1478 陶陶摘苹果升级版题目描述又是一年秋季时陶陶家的苹果树结了n nn个果子。陶陶又跑去摘苹果这次他有一个a aa公分的椅子。当他手够不着时他会站到椅子上再试试。这次与 NOIp2005 普及组第一题不同的是陶陶之前搬凳子力气只剩下s ss了。当然每次摘苹果时都要用一定的力气。陶陶想知道在s 0 s0s0之前最多能摘到多少个苹果。现在已知n nn个苹果到达地上的高度x i x_ixi椅子的高度a aa陶陶手伸直的最大长度b bb陶陶所剩的力气s ss陶陶摘一个苹果需要的力气y i y_iyi求陶陶最多能摘到多少个苹果。输入格式第1 11行两个数 苹果数n nn力气s ss。第2 22行两个数 椅子的高度a aa陶陶手伸直的最大长度b bb。第3 33行~第3 n − 1 3n-13n−1行每行两个数 苹果高度x i x_ixi摘这个苹果需要的力气y i y_iyi。输出格式只有一个整数表示陶陶最多能摘到的苹果数。输入输出样例 #1输入 #18 15 20 130 120 3 150 2 110 7 180 1 50 8 200 0 140 3 120 2输出 #14说明/提示对于100 % 100\%100%的数据n ≤ 5000 n\leq 5000n≤5000,a ≤ 50 a\leq 50a≤50,b ≤ 200 b\leq 200b≤200,s ≤ 1000 s\leq 1000s≤1000,x i ≤ 280 x_i\leq 280xi≤280,y i ≤ 100 y_i\leq 100yi≤100。代码1二维数组#includebits/stdc.husingnamespacestd;constintN500010,M100010;intn,V,v,x,a,b,h,f[N][M];intmain(){cinnV;cinab;hab;for(inti1;in;i){cinxv;for(intj0;jV;j){f[i][j]f[i-1][j];if(vjxh)f[i][j]max(f[i][j],f[i-1][j-v]1);}}coutf[n][V];return0;}代码2一维数组#includebits/stdc.husingnamespacestd;constintM100010;intn,V,v,x,a,b,h,f[M];intmain(){cinnV;cinab;hab;for(inti1;in;i){cinxv;for(intjV;jv;j--){if(xh)f[j]max(f[j],f[j-v]1);}}coutf[V];return0;}结果