求助,16和18两个点过不了

P1417 烹调方案

chenwanxi41 @ 2018-10-04 09:09:24


#include<algorithm>
#include<cstdio>
using namespace std;
long long f[1000201],maxx,t;
struct node
{
    long long a,b,c;
    double d;
}no[2001];
bool cmp(node x,node y)
{
    if(x.d<y.d) return 1;
    else return 0;
}
int main()
{
    int n;
    scanf("%lld%d",&t,&n);
//    t=read();n=read();
//    for(int i=1;i<=t;i++) f[i]=-2000000000;
//    f[0]=0;
    for (int i=1;i<=n;i++) scanf("%lld",&no[i].a);
    for (int i=1;i<=n;i++) scanf("%lld",&no[i].b);
    for (int i=1;i<=n;i++) scanf("%lld",&no[i].c);
    for (int i=1;i<=n;i++) no[i].d=no[i].c/no[i].b;
    sort(no+1,no+n+1,cmp);
    for (int i=1;i<=n;i++)
        for (int j=t;j>=no[i].c;j--)
            if (f[j-no[i].c]+(no[i].a-j*no[i].b)>f[j])
                f[j]=(long long)f[j-no[i].c]+(long long)no[i].a-(long long)j*no[i].b;
    for(int i=1;i<=t;i++) maxx=max(maxx,f[i]);
    cout<<maxx;
//  for(int i=1;i<=t;i++) cout<<f[i]<<" ";
    return 0;
}

by zymzym @ 2018-10-31 21:43:10

排序要判断的应该是 x.cy.b<y.cx.b 而不是 x.c/x.b<y.c/y.b

大概是因为整除吧...


|