2015 多校联赛 ——HDU5400（水）

Sample Input

5 2 -2 0 2 0 -2 0 5 2 3 2 3 3 3 3

 

Sample Output

12 5

求最多多少序列满足，前半部分满足d（j+1） = d（j）+d1，后半部分d（j+1）= d（j）+d2，或者只满足其中一个。

假设可以找出长度为x的序列，则有x-1 + x-2 + .... + 1种。所以从头到尾找一遍即可。

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

int num[101000];
int sta[101000];

ll p(ll n)
{
    return (1+n)*n/2;
}

int main()
{
    int n, d1, d2;

    while(scanf("%d%d%d", &n, &d1, &d2)!=EOF)
    {
        scanf("%d", num+1);
        for(int i=2; i<=n; i++)
        {
            scanf("%d", num+i);
            if(num[i]==(num[i-1]+d1)) sta[i] = 1;
            else if(num[i]==(num[i-1]+d2)) sta[i] = 2;
            else sta[i] = 0;
        }
//        for(int i=1; i<=n; i++) printf("%d ", num[i]);
//        for(int i=1; i<=n; i++) printf("%d ", sta[i]);

        ll re = 0;
        int cur = 1;
        while(cur<=n)
        {
            int ccur = cur+1;
            bool flag = true;
            while(ccur<=n)
            {
                if(sta[ccur]==0) break;
                else if(sta[ccur]==1) ccur++;
                else if(sta[ccur]==2)
                {
                    while(ccur<=n)
                    {
                        if(sta[ccur]==2) ccur++;
                        else
                        {
                            flag = false;
                            break;
                        }
                    }
                }
                if(!flag) break;
            }
            re += p(ccur-cur-1);
            if((ccur-cur)>1)
                cur = ccur - 1;
            else cur = ccur;
            if(ccur>n) break;
        }

        printf("%I64d
", re+n);
    }
    return 0;
}