第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）Stone Game

68 阅读 0 评论 45 点赞

我是靠谱客的博主落后小蚂蚁，这篇文章主要介绍第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）Stone Game，现在分享给大家，希望可以做个参考。

有 1 个石子的有 a 堆，2 个石子的有 b 堆，3 个石子的有 c 堆，每次合并任意两堆石子，花费为 (x%3)*(y%3)，x y 为石子的个数，问将所有的石子合并成一堆石子之后的花费最小是多少

将 1 2 先合起来，然后看 1 剩下还是 2 剩下，再用剩下的与 3 合并，这样是最优的

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main()
{
    ll a,b,c;
    while(~sll(a)){
        sll(b),sll(c);
        ll ans=0,res=0,k=0;
        if(a>b){
            ans=b*2;
            k=(a-b)/3;
            res=(a-b)%3;
            ans+=k*3;
            if(res==2) ans++;
        }
        else{
            ans=a*2;
            k=(b-a)/3;
            res=(b-a)%3;
            ans+=6*k;
            if(res==2) ans+=4;
        }
        pll(ans);
    }
    //PAUSE;
    return 0;
}