解题思路:
我们观察式子可以发现,可以把每一个数提出来,以a1到a5为例
S=a1*(a2+a3+a4+a5)+a2*(a3+a4+a5)+a3*(a4+a5)+a4*a5
这样很容易想到前缀和,我们可以通过前缀和来得到括号里面的数,这样时间复杂度就降到了O(n)
参考代码:
#include <stdio.h> long long p[200007]; long long dp[200007];//开到long long 来存放这些数之和 int main (){ int i,j; int n; long long z=0;//注意开到long long scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&p[i]); if(i==0)dp[i]=p[i]; else dp[i]=dp[i-1]+p[i];//前缀和数组 } for(i=0;i<n;i++){ z+=p[i]*(dp[n-1]-dp[i]);//dp[n-1]-dp[i]即为()里的数 } printf("%lld",z); return 0; }
还有另一种算法,时间复杂度是O(n)但是不需要开辟数组。
代码如下:
#include <stdio.h> int main () { int i; int n,m; long long k=0,z=0; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&m); z+=k*m; k+=m; } printf("%lld",z); return 0; }
这样的做法就是把式子拆成:
S=a2*a1+a3*(a2+a1)+a4*(a3+a2+a1)+a5*(a4+a3+a2+a1)
通过调整式子结构,就可以一边求前缀和一边相加了。
0.0分
291 人评分
校门外的树 (C++代码)浏览:868 |
字符串的输入输出处理 (C语言代码)浏览:656 |
点我有惊喜!你懂得!浏览:4105 |
震宇大神的杀毒软件 (C++代码)浏览:1110 |
大神老白 (C语言代码)浏览:640 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:519 |
P1000 (C语言代码)浏览:868 |
核桃的数量 (C语言代码)浏览:668 |
【亲和数】 (C语言代码)浏览:597 |
简单的a+b (C语言代码)浏览:543 |
指针原来是套娃的 2024-04-02 10:39:38 |
哈哈 让我看了好几遍题解,我写的就是这个式子呀