BestCoder Sequence

1 1
1
5 3
4 5 3 2 1

1
3

Hint
For the second case, {3},{5,3,2},{4,5,3,2,1} are Bestcoder Sequence.

————————————————————————————————————————————

<strong><span style="font-size:18px;">#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 100001
#define base 40000
using namespace std;
int a[M],dp[M];
int main()
{
    int n,m,x;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            if(a[i]==m) x=i;
        }
        memset(dp,0,sizeof dp);
        int ans=0;
        for(int i=x+1;i<n;++i){
            if(a[i]>m) ans++;  //大的加小的减
            else ans--;
            dp[ans+base]++;    //记录出现该状态的次数
        }
        ans=++dp[base];<span style="white-space:pre">		</span>//当状态数为base，才满足中位数
        int tmp=0;
        for(int i=x-1;i>=0;--i){
            if(a[i]>m) tmp++;
            else tmp--;
            ans+=dp[-tmp+base];<span style="white-space:pre">		</span>状态相加为base的个数
        }
        cout<<ans<<endl;
    }
    return 0;
}</span></strong>

1242

HDU 4908——BestCoder Sequence,布布扣,bubuko.com

HDU 4908——BestCoder Sequence

原文：http://blog.csdn.net/u014141559/article/details/38364655