hdu 4091 数学思维题贪心

/*

参看博客地址：http://blog.csdn.net/oceanlight/article/details/7857713

重点是取完最优的后剩余的rest=n%lcm+lcm;中性价比小的数目num<lcm/性价比小的体积，因为如果大于的话

肯定可以由性价比好的替换。

然后枚举。从体积大的开始枚举次数少。

注意64位

*/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define ll  __int64

ll gcd(ll a,ll b) {

if(b==0)return a;

return gcd(b,a%b);

}

ll lcm(ll a,ll b) {

return a/gcd(a,b)*b;

}

int main() {

   ll t,n,i,k=0,m,a,av,b,bv,aa,maxx,d;

  scanf("%I64d",&t);

  while(t--){

    scanf("%I64d%I64d%I64d%I64d%I64d",&n,&av,&a,&bv,&b);

    m=lcm(av,bv);

    aa=0;maxx=-1;

    if(n/m) {//如果可以lcm<=n

    if(a*bv>b*av)

           aa+=m/av*(n/m-1)*a;

           else

           aa+=m/bv*(n/m-1)*b;

    }

    if(n/m)//如果lcm<=n

    m+=n%m;

    else

        m=n;

    if(av<bv) {d=av;av=bv;bv=d;d=a;a=b;b=d;}//av。a记录体积大的

    for(i=0;i<=m/av;i++) {//从体积大的开始枚举

        if(maxx<aa+i*a+(m-i*av)/bv*b)

            maxx=aa+i*a+(m-i*av)/bv*b;

    }

    printf("Case #%I64d: %I64d\n",++k,maxx);

  }

return 0;}
巴特西

hdu 4091 数学思维题贪心

最新文章

热门文章
