解题思路:
我们观察式子可以发现,可以把每一个数提出来,以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分
140 人评分
人见人爱A+B (C语言代码)浏览:625 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:470 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:660 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:548 |
C语言训练-亲密数 (C语言代码)浏览:682 |
最小公倍数 (C语言代码)浏览:1025 |
1908题解浏览:633 |
星期判断机 (C语言代码)浏览:856 |
分糖果 (C语言代码)浏览:911 |
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:649 |