DP ZOJ 3872 Beauty of Array

 /*

     DP：dp 表示当前输入的x前的包含x的子序列的和，

         求和方法是找到之前出现x的位置(a[x])的区间内的子序列；

         sum 表示当前输入x前的所有和；

         a[x] 表示id；

     详细解释：http://blog.csdn.net/u013050857/article/details/45285515

 */

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <map>

 #include <set>

 using namespace std;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN];

 int main(void)        //ZOJ 3872 Beauty of Array

 {

     //freopen ("D.in", "r", stdin);

     int t, n;

     scanf ("%d", &t);

     while (t--)

     {

         memset (a, , sizeof (a));

         scanf ("%d", &n);

         int x;    long long dp = , sum = ;

         for (int i=; i<=n; ++i)

         {

             scanf ("%d", &x);

             dp = (i - a[x]) * x + dp;

             sum += dp;

             a[x] = i;

         }

         printf ("%lld\n", sum);

     }

     return ;

 }