列表

详情


QQ10. 石子合并

描述

小Q和牛博士在玩一个石子合并的游戏,初始一共有n堆石子,每堆石子有w[i]个石子。小Q和牛博士他们需要对石子堆进行合并,每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆,这次合并得分为x*y,当只剩下一堆石子的时候游戏结束。

、小Q和牛博士希望采取优秀的策略获得最大得分,希望你能来帮他们算算最大得分多少。

输入描述

输入包括两行,第一行一个正整数n(2≤n≤100)。

第二行包括n个正整数w[i](1≤w[i]≤100),即每堆石子的个数。

输出描述

输出一个正整数,即小Q和牛博士最大得分是多少。

示例1

输入:

3
1 2 3

输出:

11

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 360KB, 提交时间: 2020-09-04

#include <stdio.h>

int main()
{
    int n,ans=0;
    int w[100]={0};

    scanf("%d%d",&n,&w[0]);
    for(int i=1;i<n;i++)
    {
        scanf("%d",&w[i]);
        ans+=w[i-1]*w[i];
        w[i]+=w[i-1];
    }
    printf("%d",ans);

    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-08-21

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,cur,sum=0;
    while(scanf("%d",&n)!=EOF){
        int *num = (int *)malloc(n*sizeof(int));
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
        }
        if(n==2){
            printf("%d\n",num[0]*num[1]);
        }else{
            for(int i= 1;i<n;i++)
            {
                cur=i;
                while(num[cur]-num[cur-1]<0 && cur>0)
                {
                    int temp = num[cur];
                    num[cur]=num[cur-1];
                    num[cur-1] = temp;
                    cur--;
                }
            }
            for(int i= n-1;i>=1;i--)
            {
                
                sum+=num[i]*num[i-1];
                num[i-1]=num[i]+num[i-1];
            }
            printf("%d\n",sum);
        }
        free(num);
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-08-21

#include<stdio.h>
int main()
{
    int n,i,j,s=0,g=0;
    scanf("%d",&n);
    int w[n];
 /*   for(i=0;i<n-1;i++)
    {
        scanf("%d",&w[i]);
    }*/
    for(j=0;j<n;j++)
    {   scanf("%d",&w[j]);
        s=s+w[j-1];
        g=g+s*w[j];
    }
    printf("%d\n",g);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2019-05-26

#include <stdio.h>
int main() {
    int num = 0;
    scanf("%d", &num);
    int res = 0;
    int sum = 0;
    int t = 0;
    int i = 0;
    for(i = 0; i < num; i++) {
        scanf("%d", &t);
        res += sum * t;
        sum += t;
    }
    printf("%d\n", res);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2019-03-11

#include <stdio.h>
int main() {
    int num = 0;
    scanf("%d", &num);
    int res = 0;
    int sum = 0;
    int t = 0;
    int i = 0;
    for(i = 0; i < num; i++) {
        scanf("%d", &t);
        res += sum * t;
        sum += t;
    }
    printf("%d\n", res);
    return 0;
}

上一题