编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 494ms

├ 测试数据 10：答案正确... 478ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1188ms

考验人的耐性。怎么这么慢？

AC100题。 庆祝一下！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 322ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：790ms

祝贺自己:AC100题.!!

速度不太快..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：97ms

这就是速度！！！

这道题，枚举A0,B0，再扫描。复杂度为O(N*N*N).但是，可以发现，两次枚举的结果存在一定的公共段，充分利用上次的结果可以把复杂度降为O(N*N).

这个貌似不太像DP吧。。

扫描下就可以 平摊~~所以O(N*N)

楼下的。。。虽然你说的很详细。。但是我还是看不懂。。。。。

枚举a0,递增枚举b0,搞一个以ai*c1+bi*c2的队列，随着b0递增，去掉不符合条件的梨子，可以用hash记录一下

按a,b,c1*a+c2*b排序,然后搞个队列~~~

怎么做？

挖靠 被误解了 晕死掉 原来要 梨子种类都满足 我还以为满足条件就可以 算1个

菜.....接着编过.....难...

被搞成我们省选了。。。无言

竟然没看出来是DP……

简单题。直接做即可。O(N^2)

难!

够难!

非常难!

感觉题目描述不清楚/。。。。

将梨子分别按照A、B以及C1*A+C2*B递增顺序排序。

记录“以按照A排序处于第I位的梨子的A为A0，以按照B排序处于第J位的梨子的B为B0”所能取到的最大梨子数以及最小A值、最小B值、最大C1*A+C2*B在相应序列里的位置。

则状态从(I, J-1)或(I-1, J)转移到(I, J)只需在C1*A+C2*B序列上继续向前推进，在A、B序列上减掉因为A0或B0增大而变为不能取到的梨子即可。

时间复杂度为O(N^2)乘个系数。

PS：本人好不容易等到Puppy……终于AC！！！要不TLE…………

PS/2:求楼下大牛的思路......

不用DP也可以过，不过思路有点麻烦

PS：求DP的思路

枚举a0,计算b0,dp+扫描 效率n^2

这题怎么能没人过呢？

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=2005;
struct node
{
    int a,b,s;
}p[MAXN];
int c1,c2,c3;
int ans;
int n;

inline bool cmp(const node&a,const node&b)
{
    return a.s<b.s;
}

void init()
{
    scanf("%d",&n);
    scanf("%d%d%d",&c1,&c2,&c3);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i].a,&p[i].b);
        p[i].s=p[i].a*c1+p[i].b*c2;
    }
}

int main()
{
    init();
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int a0=p[i].a;  int b0=p[i].b;  int cur=i;
        int tot=0;
        while(p[cur++].s<=c1*a0+c2*b0+c3&&cur<=n)
            tot++;
        ans=max(ans,tot);
    }
    cout<<ans<<endl;
    return 0;
}