ZOJ 3872 Beauty of Array

 1 /**
 2 Author: Oliver
 3 ProblemId: ZOJ 3872 Beauty of Array
 4 */
 5 /*
 6 需求：
 7 求beauty sum，所谓的beauty要求如下： 
 8 1·给你一个集合，然后把所有子集合的美丽和求出来；
 9 2·上例子，2.3.3.->2.  3.  3.  2.3.  3.  2.3.
10 思路：
11 1·既然要连续的，暴力也会爆，那么自然而然的优化，朝着递推想一下；
12 2·哥们把之前的算好了，那我们是不是可以用算好的值来求现在的的需要呢；
13 3·想好了，但是过程我不造该怎么说;
14 步骤： 。。。
15 */
16 #include <cstdio>
17 #include <cstring>
18 #include <algorithm>
19 using namespace std;
20 
21 const int MAXM = 100000+10;
22 const int MAXN = 1000000+10;
23 int F[MAXN],a[MAXM];
24 int main()
25 {
26     int n,T;
27     scanf("%d",&T);
28     while(T--)
29     {
30         scanf("%d",&n);
31         memset(F,0,sizeof F);
32         long long ans=0,sum=0;
33         for(int i=1;i<=n;i++){
34         scanf("%d",&a[i]);
35         if(F[a[i]])sum-=F[a[i]]*a[i];
36         ans+=sum+=i*a[i];
37         
38         F[a[i]]=i;
39         }
40         printf("%lld\n",ans);
41     }
42 }