一、问题描述
二、问题简析
看完题目,肯定会想到贪心,但是这题不需要贪心也能解决。
假设有 4 4 4 颗石子: a , b , c , d a,~b,~c,~d a, b, c, d。我们随意组合,得到结果:
a n s = b c + a ( b + c ) + ( a + b + c ) d = a ( b + c + d ) + b ( c + d ) + c d \begin{split} ans&=bc+a(b+c)+(a+b+c)d \\ &=a(b+c+d)+b(c+d)+cd \end{split} ans=bc+a(b+c)+(a+b+c)d=a(b+c+d)+b(c+d)+cd
如果尝试其它的方式,得到的结果也是一样的。我们可以推测, n n n 颗石子的结果为
a n s = ∑ i = 0 n − 2 ( a i ∗ ∑ j = i + 1 n − 1 a j ) ans=\sum_{i=0}^{n-2}(a_i * \sum_{j=i+1}^{n-1}a_j) ans=i=0∑n−2(ai∗j=i+1∑n−1aj)
我们可以采用前缀和来优化 ∑ j = i + 1 n − 1 a j \sum_{j=i+1}^{n-1}a_j ∑j=i+1n−1aj。
三、AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int quickin(void)
{
int ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
const int MAX = 1e5 + 3;
ll A[MAX], n, B[MAX];
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
n = quickin();
ll tmp = 0;
for (int i = 0; i < n; i++)
{
A[i] = quickin();
tmp += A[i];
B[i] = tmp;
}
ll ans = 0;
for (int i = 0; i < n - 1; i++)
{
ans += A[i] * (B[n - 1] - B[i]);
}
cout << ans << endl;
return 0;
}
完