本文主要是介绍HDU 5328 Problem Killer,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem Killer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 252 Accepted Submission(s): 97
Now you have n problems, the i -th problem's difficulty is represented by an integer ai ( 1≤ai≤109 ).
For some strange reason, you must choose some integer l and r ( 1≤l≤r≤n ), and solve the problems between the l -th and the r -th, and these problems' difficulties must form an AP (Arithmetic Progression) or a GP (Geometric Progression).
So how many problems can you solve at most?
You can find the definitions of AP and GP by the following links:
https://en.wikipedia.org/wiki/Arithmetic_progression
https://en.wikipedia.org/wiki/Geometric_progression
For each test case, the first line contains a single integer n , the second line contains n integers a1,a2,?,an .
T≤104,∑n≤106
2 5 1 2 3 4 6 10 1 1 1 1 1 1 2 3 4 5
4 6
/* ***********************************************
Author :
Created Time :2015/7/30 13:57:52
File Name :2.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1000000000
#define maxn 1000000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int n;
int a[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int t;
cin>>t;
while(t--){
scanf("%d",&n);
int d=-INF-INF-10;
double q=0.0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int Max=1;
int MMax=1;
int x=1,y=1;
for(int i=2;i<=n;i++){
int d1=a[i]-a[i-1];
if(d1==d){
x++;
if(x>Max){
Max=x;
}
}
else {
d=d1;
x=1;
}
}
for(int i=2;i<=n;i++){
double q1=a[i]*1.0/(a[i-1]*1.0);
if(q1==q){
y++;
if(y>MMax){
MMax=y;
}
}
else{
q=q1;
y=1;
}
}
if(n==1)printf("%d\n",1);
else printf("%d\n",max(Max,MMax)+1);
}
return 0;
}
这篇关于HDU 5328 Problem Killer的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!