FZU-2252 磁石合成

我不是女神ヾ 2022-02-09 11:25 86阅读 0赞

> 题目衔接：[http://acm.fzu.edu.cn/problem.php?pid=2252][http_acm.fzu.edu.cn_problem.php_pid_2252]

> **Problem 2252 Yu-Gi-Oh!**
> 
> ### Accept: 203    Submit: 1021   Time Limit: 1000 mSec    Memory Limit : 32768 KB ###
> 
> ## ![prodesc.gif][] Problem Description ##
> 
> 另一个平行宇宙的YellowStar，是一名游戏王决斗者，某一天它正在进行一场决斗，它的场面上拥有A只磁石战士a，B只磁石战士β，C只磁石战士γ。
> 
>  
> 
> 现在它要把这些怪物进行一波强力的融合，并且它知道：
> 
>  
> 
> 将磁石战士a和β融合成为磁石战士aβ，战斗力为AB
> 
>  
> 
> 将磁石战士a和γ融合成为磁石战士aγ，战斗力为AC
> 
>  
> 
> 将磁石战士β和γ融合成为磁石战士βγ，战斗力为BC
> 
>  
> 
> 由于YellowStar是一名人生经验丰富的决斗者，因此它在本回合可以进行无限次的融合。它想知道经过融合它能得到最大的战斗力是多少。
> 
> ## ![prodesc.gif][] Input ##
> 
> 第一行输入T，表示有T组样例(T <= 20)
> 
>  
> 
> 每组样例为两行，每行3个数字
> 
> 第一行为A, B, C (1 <= A, B, C <= 1e6)，表示每种怪物的数量
> 
> 第二行为AB, AC, BC (1 <= AB, AC, BC <= 1e6)，分别表示AB，AC，BC融合之后的战斗力

>  ![prodesc.gif][] Output
> 
> 每组样例输出一个数字表示答案
> 
> ## ![prodesc.gif][] Sample Input ##
> 
> 2 1 1 1 1 2 3 10 23 15 5 4 9
> 
> ## ![prodesc.gif][] Sample Output ##
> 
> 3 175
> 
> ## ![prodesc.gif][] Hint ##
> 
> 第一个样例由于每种怪物只有一只，因此它选择融合出战斗力最为强大的磁石战士βγ，答案为3
> 
> long long类型请用%I64d输出
> 
> ## ![prodesc.gif][] Source ##
> 
> FOJ有奖月赛-2017年4月（校赛热身赛）

思路：刚开始想的是直接取较大的两个，算出结果就好了，然后wa了，仔细考虑了一下发现了一些其它的情况，这里我们需要枚举来算，例如这个样例：10 30 25     21 20 25 如果你用那个简单思路来答案是655，但是最大值却可以达到693

具体看代码。。

代码：

/*
    题目大意:
    
    
    思路：
    
    */
    #include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include <vector>
    #include<cstring>
    #include<sstream>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    #define ul unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define pp printf("\n");
    #define pn(a) printf("%d\n",a);
    #define bug printf("mmp\n");
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=2e6+10;
    const double pi=acos(-1.0);
    const int N=1001;
    const int mod=1e9+7;
    int main()
    {
        T()
        {
            ll a,b,c;
            scanf("%I64d%I64d%I64d",&a,&b,&c);
            ll ab,ac,bc;
            scanf("%I64d%I64d%I64d",&ab,&ac,&bc);
            ll minn=min(a,b);
            ll ans=0;
            for(int i=0;i<=minn;i++)
            {
                ll sum=i*ab;
                ll mina=a-i;
                ll minb=b-i;
                ll minc=c;
                if(ac>bc)
                {
                    if(mina<minc)
                    {
                        sum+=mina*ac;
                        minc-=mina;
                        sum+=min(minb,minc)*bc;
                    }
                    else
                    {
                        sum+=ac*minc;
                    }
                }
                else
                {
                    if(minb<minc)
                    {
                        sum+=bc*minb;
                        minc-=minb;
                        sum+=min(minc,mina)*ac;
                    }
                    else
                        sum+=bc*minc;
                }
                ans=max(ans,sum);
            }
            printf("%I64d\n",ans);
        }
        return 0;
    }

[http_acm.fzu.edu.cn_problem.php_pid_2252]: http://acm.fzu.edu.cn/problem.php?pid=2252
[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif