数学题
当n=2时:ab
当n=3时:ab+(a+b)c=ac+(a+c)b=bc+(b+c)a=ab+ac + bc
当n=4时:ab+(a+b)c+(a+b+c)d=ac+(a+c)b+(a+c+b)d=.....=ab+ac+ad+ bc+bd +cd
以此类推 每个数分别与后面的所有数相乘之和即可
也就等于
当n=2时: ab
当n=3时:ab+ac+bc=ab+(a+b)c
当n=4时:ab+ac+ad+bc+bd+cd=ab+(a+b)c+(a+b+c)*d
$O(n)$
C++ 代码
#include<iostream>
using namespace std;
int n,x;
int main()
{
cin>>n;
long long int sum=0,res=0;
for(int i=0;i<n;i++){
cin>>x;
sum+=res*x;
res+=x;
}
cout<<sum<<endl;
return 0;
}
还以为是基础课里讲的石子合并呢,没想到想复杂了😂😂
哎, 我也以为是区间dp。。。可能还是要看数据范围吧555,1e5的数据,区间dp的复杂度好像还是有点高的
数学归纳法yyds
orz
###Orz
##Orz
#Orz
怎么发现这个性质的。。。模拟了下数据还是挖掘了某种性质
orz
搞了半天是数论。。。。。。
是我想太多
Orz
orz
O.o
Orz
666666666666
我还以为每次是最小的两个石头胶在一起呢
其实按这个思路也是可以AC的,只不过longlong要记得开
为啥我这样写过不了 是O(n^2logn)
直接用合并果子那个代码就行了,把优先队列改一下
把优先队列里面的int改成longlong
好滴谢谢
不可以吧 他是合并相邻俩个 不是任意俩个合并
牛逼
太牛了,这道题好骗人哈哈
# orz orz orz
666666
orz
orz
Orz