算法
(前缀和) $O(n)$
首先要说的是 : 这是一道诈骗题!!!
那么为什么呢?
假设有3个 : a,b,c;
有两种组合方式 : ((a,b)c) 和 (a,(b,c))
ans1 : (ab) + ((a+b)c) = ab+ac+bc
ans2 : (bc) + ((b+c)a) = ab+ac+bc
–> ans1 = ans2;
然后从前往后模拟就好了!!!
时间复杂度
O(n)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n ; cin >> n ;
// 乘积 怎么弄都是一样的 -- > 所以从前往后就好
int x ; cin >> x; n -- ;
int ans = 0 , ps = x ; // 这里直接用ps来模拟前缀和了
while(n--){
cin >> x ;
ans += ps * x ;
ps += x ;
}
cout << ans << endl ;
}