扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
题目链接：https://www.luogu.com.cn/problem/P8772
目前创新互联建站已为1000多家的企业提供了网站建设、域名、网站空间、网站托管运营、企业网站设计、屏边网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。我是在洛谷里做到这题的。
因为刚接触算法在练习前缀和，我直接再洛谷上搜索了关于前缀和的题看到这个题。
由于我一开始就知道这题要用前缀和做，所以我做起来就不难了，关键是怎么找到里面运用了前缀和的地方。
题目只给了一个式子，我们首先看不到任何破解之法，就可以带入特定的值，就像题中的案例带入的是4，将4带入后写出完整的式子是
s = a1*a2 + a1*a3 + a1*a4
+ a2*a3 + a2* a4
+a3*a4
将公因式提取出来就是
s = a1*（a2 + a3 + a4）
+ a2*（a3 + a4）
+a3*a4
可以看到括号内就是一个前缀和的形式，这样就和前缀和联系起来了。
但是说实话，我还是不清楚怎么一看到题目就知道要运用到前缀和，如果有网友知道的话可以在评论区告知一声吗？提前说声谢谢啦。
我用的是java写的，代码如下
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 10];
long[] s = new long[n + 10];
long sum = 0;
for(int i = 1; i<= n; i++){
a[i] = sc.nextInt();
s[i] = s[i - 1] + a[i];
}
for(int i = 1; i<= n; i++){
sum += a[i] * (s[n] - s[i]);
}
System.out.println(sum);
}
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网