MYF

HDU 5400 Arithmetic Sequence

Posted on | In | | Visitors

题目链接

HDU 5400

记忆化搜索 （其实我不知道这个算不算DP）

题目分析

题目大意

给定n个数和d1和d2，问这n个数中存在多少个子区间，使子区间具有这样的性质：子区间内可以分为a个和b个数的序列，a和b均可为零，前a个数为公差为d1的等差序列，后b个数为公差为d2的等差数列。

解析

比赛的时候想法有点挫，统计出a和b的长度，然后强行算半天。

其实大可不必这样，直接记忆化搜索，比如有长度为l的公差为d的序列，那么第一个数只有一个次数1，第二个数为2，表示是它本身以及它和前一个数所形成的序列，同理，第三个数为3，表示本身，他本身和前一个数，他本身和前两个数形成的3种序列，最后，遍历每一个位置，只需要将在该点形成的两个公差相乘求和即可。

说的很晦涩，其实如果对于下标1, 2, 3, 4, 5来讲，比如前三个数字符合公差为d1的等差序列，后三个数符合公差为d2的等差数列，那么记忆化搜索出来的两个数组即为1, 2, 3, 1, 1和1, 1, 3, 2, 1，第一位对应数字相乘表示1，有一个，即为本身，第二位相乘表示2，有两个，即本身和前一个，第三位相乘为9，表示所有包含该点的情况，左边可以有三个数字，三种，右边有三个数字，三种，相乘即为3 * 3 = 9。

比赛时的代码写的真的好挫。。。

代码

赛后代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int a[maxn],l[maxn],r[maxn];
int main(){
    int n,d1,d2;
    while (scanf("%d%d%d",&n,&d1,&d2)!=EOF) {
        for (int i=0; i<n; i++)
            scanf("%d",&a[i]);
        
        for (int i=0; i<n; i++)
            if (i&&a[i]-a[i-1]==d1)
                l[i]=l[i-1]+1;
            else
                l[i]=1;
        
        for (int i=n-1; i>=0; i--)
            if (i!=n-1&&a[i+1]-a[i]==d2)
                r[i]=r[i+1]+1;
            else
                r[i]=1;
        
        ll sum=0;
        if (d1==d2)
            for (int i=0; i<n; i++)
                sum+=(ll)l[i];
        else
            for (int i=0; i<n; i++)
                sum+=(ll)l[i]*r[i];

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

赛时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
ll a[maxn];
struct node{
    ll l,r,len;
    node(int ll=1,int rr=1):l(ll),r(rr){
        len=rr-ll+1;
        //printf("%d %d\n",ll, rr);
    }
    ll sum(){
        return len*(len+1)/2-len;
    }
    void show() {
    	cout<<l<<" "<<r<<" "<<endl;
    }
};
int main(){
    int n;
    ll d1,d2,diff;
    while (cin>>n>>d1>>d2) {
        for (int i=1; i<=n; i++) {
            scanf("%I64d",a+i);
        }
        queue<node> q1,q2;
        
        
        ll cnt=0;
        for (int i=2; i<=n; i++) {
            diff=a[i]-a[i-1];
            if (diff==d1) {
                cnt++;
            }
            else{
                if (cnt) {
                    q1.push(node(i-1-cnt,i-1));
                }
                cnt=0;
            }
        }
        if (cnt) {
            q1.push(node(n-cnt,n));
        }
        
        if (d1==d2) {
            ll ans=n;
            while (!q1.empty()) {
                ans+=q1.front().sum();
                q1.pop();
            }
            printf("%I64d\n",ans);
            continue;
        }
        cnt=0;
        for (int i=2; i<=n; i++) {
            diff=a[i]-a[i-1];
            if (diff==d2) {
                cnt++;
            }
            else{
                if (cnt) {
                    q2.push(node(i-1-cnt,i-1));
                }
                cnt=0;
            }
        }
        if (cnt) {
            q2.push(node(n-cnt,n));
        }
        
        ll ans=n;
        bool f1,f2;
        f1=f2=false;
        node now1,now2;
		while (!q1.empty()&&!q2.empty()) {
			now1 = q1.front();
			now2 = q2.front();
            if (now1.r==now2.l) {
                ans+=(now1.len-1)*(now2.len-1)+now1.sum()+now2.sum();
                f1=f2=true;
            }
            else if (now1.r<now2.l){
                ans+=now1.sum();
                f1=true;
                f2=false;
            }
            else{
                ans+=now2.sum();
                f1=false;
                f2=true;
            }
            if(f1)q1.pop();
            if(f2)q2.pop();
        }
        while (!q1.empty()) {
            ans+=q1.front().sum();
            q1.pop();
        }
        while (!q2.empty()) {
            ans+=q2.front().sum();
            q2.pop();
        }

        printf("%I64d\n",ans);
        
    }
    return 0;
}