递推DP HDOJ 5328 Problem Killer-白红宇

递推DP HDOJ 5328 Problem Killer

阅读量：6692 次

发布时间：2019-06-25

本文共 1181 字，大约阅读时间需要 3 分钟。

1 /* 2     递推DP: 如果a, b, c是等差数列，且b, c, d是等差数列，那么a, b, c, d是等差数列，等比数列同理 3             判断ai-2, ai-1, ai是否是等差(比)数列，能在O(n)时间求出最长的长度 4 */ 5 #include 
     
       6 #include 
      
        7 #include 
       
         8 #include 
        
          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 Killer18     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", 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\n", ans);32         }33     }34 35     return 0;36 }