QQ10. 石子合并
描述
小Q和牛博士在玩一个石子合并的游戏,初始一共有n堆石子,每堆石子有w[i]个石子。小Q和牛博士他们需要对石子堆进行合并,每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆,这次合并得分为x*y,当只剩下一堆石子的时候游戏结束。
、小Q和牛博士希望采取优秀的策略获得最大得分,希望你能来帮他们算算最大得分多少。
输入描述
输入包括两行,第一行一个正整数n(2≤n≤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; }