DP ZOJ 3872 Beauty of Array-白红宇

DP ZOJ 3872 Beauty of Array

阅读量：6265 次

发布时间：2019-06-22

本文共 961 字，大约阅读时间需要 3 分钟。

1 /* 2     DP：dp 表示当前输入的x前的包含x的子序列的和， 3         求和方法是找到之前出现x的位置(a[x])的区间内的子序列； 4         sum 表示当前输入x前的所有和； 5         a[x] 表示id； 6     详细解释：http://blog.csdn.net/u013050857/article/details/45285515 7 */ 8 #include 
     
       9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           15 #include 
            
             16 using namespace std;17 18 const int MAXN = 1e5 + 10;19 const int INF = 0x3f3f3f3f;20 int a[MAXN];21 22 int main(void) //ZOJ 3872 Beauty of Array23 {24 //freopen ("D.in", "r", stdin);25 26 int t, n;27 scanf ("%d", &t);28 while (t--)29 {30 memset (a, 0, sizeof (a));31 scanf ("%d", &n);32 33 int x; long long dp = 0, sum = 0;34 for (int i=1; i<=n; ++i)35 {36 scanf ("%d", &x);37 dp = (i - a[x]) * x + dp;38 sum += dp;39 a[x] = i;40 }41 42 printf ("%lld\n", sum);43 }44 45 46 return 0;47 }