递推DP HDOJ 5328 Problem Killer

 1 /*
 2     递推DP: 如果a, b, c是等差数列，且b, c, d是等差数列，那么a, b, c, d是等差数列，等比数列同理
 3             判断ai-2, ai-1, ai是否是等差(比)数列，能在O(n)时间求出最长的长度
 4 */
 5 #include <cstdio>
 6 #include <algorithm>
 7 #include <cstring>
 8 #include <cmath>
 9 using namespace std;
10 
11 typedef long long ll;
12 const int MAXN = 1e6 + 10;
13 const int INF = 0x3f3f3f3f;
14 ll a[MAXN];
15 int dp1[MAXN], dp2[MAXN];
16 
17 int main(void)  {       //HDOJ 5328 Problem Killer
18     int T;  scanf ("%d", &T);
19     while (T--) {
20         int n;  scanf ("%d", &n);
21         for (int i=1; i<=n; ++i)    scanf ("%I64d", &a[i]);
22         if (n <= 2) printf ("%d
", n);
23         else    {
24             for (int i=1; i<=n; ++i)    dp1[i] = dp2[i] = 2;
25             int ans = 2;
26             for (int i=3; i<=n; ++i)    {
27                 if (a[i-2] + a[i] == a[i-1] * 2)    dp1[i] = dp1[i-1] + 1;
28                 if (a[i-2] * a[i] == a[i-1] * a[i-1])   dp2[i] = dp2[i-1] + 1;
29                 ans = max (ans, max (dp1[i], dp2[i]));
30             }
31             printf ("%d
", ans);
32         }
33     }
34 
35     return 0;
36 }
编译人生，运行世界！