E - 小晴天老师系列——我有一个数列！

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Submit Status

Problem Description

小晴天：“我有一个数列！”

小晴天：“我还要有很多很多的数列！”

于是小晴天就把这个数列的所有连续子数列写出来。

然后小晴天把每个连续子数列中的最大的数写出来。

那么，有多少个比K大呢？

Input

多组数据，首先是一个正整数t(t<=100)，表示数据的组数

对于每组数据，首先是两个整数n(1<=n<=200000)，K(0<=K<=10^9).，但所有数据中的n之和不超过1000000.

接下来是n个整数a[i](1<=a[i]<=10^9)

Output

对于每组数据，输出一个整数，表示最大元素大于K的连续子序列的个数。

Sample Input

Sample Output

3

5

Hint

对于样例一，共有6个连续子序列{1}{2}{3}{1,2}{2,3}{1,2,3}（注意{1,3}不满足题意，因为不连续）

其中最大元素大于2的共有3个{3}{2,3}{1,2,3}

对于样例二，大于1的连续子序列共有5个，{2}{3}{1,2}{2,3}{1,2,3}

题意：

对于输入的每一个数列，计算该数列的每一个子序列中最大的元素大于所给定的数的个数.

(PS:刚开始还以为是计算的是不一样的子序列，结果后来才知道1212中前面{1,2}和后面的{1,2}算作是两个不同的子序列，不是算作同一个子序列囧囧囧.)

用DP[i]来保存的以i为结符合条件的子序列的最大数量，

所以符合条件的子序列=全部的DP[i]相加。

所以

if（Num[i]>K）

　　　　DP[i]=i+1;

　else

　　　　DP[i]=DP[i-1];

 #include <algorithm>

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 using namespace std;

 int Num[];

 int DP[];

 int main()

 {

     int T,i,j,SUM;

     int Max,N,K,MAX,k;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&N,&Max);

         for(i=,SUM=;i<N;i++)

         {

             DP[i]=;        /*初始化DP[]*/

             scanf("%d",&Num[i]);

         }

         for(i=;i<N;i++)

         {

             if(Num[i]>Max)  /*符合条件的话*/

             {

                 DP[i]=i+;  /*最大数量等于他前面数的个数以及自己*/

             }

             else

             {

                 DP[i]=DP[i-];  /*否则等于它前一个数的最大值*/

             }

             SUM+=DP[i]; /*计算总和*/

         }

         printf("%d\n",SUM);     /*输出答案*/

     }

     return ;

 }

秒客网

E - 小晴天老师系列——我有一个数列！