codevs 1006 等差数列
2024-09-01 07:29:37
提交地址:http://codevs.cn/problem/1006/
1006 等差数列
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.
输入描述 Input Description
第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.
输出描述 Output Description
对于每个输入数据,输出你所找出的最长等差数列的长度
样例输入 Sample Input
7
3
8
4
5
6
2
2
样例输出 Sample Output
5
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm> #define N 100+10 using namespace std; int n;
int a[N];
int ans=;
int maxn=-;
bool visited[N]; //防止重复搜索 void dfs(int,int,int); int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
if(n==||n==)
{
printf("%d",n);
return ;
}
sort(a+,a+n+);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
dfs(j,a[j]-a[i],i);
if(ans>maxn)
maxn=ans;
ans=;
memset(visited,,sizeof(visited));
}
printf("%d",maxn);
return ;
} void dfs(int x,int d,int last)//分别表示:搜到的位置,公差,上次的位置
{
if(x>n) return ;
if(visited[x]) return;
if(a[x]-a[last]!=d) return;
ans++;
for(int i=;i<=n-x;i++)
{
visited[x]=true;
dfs(x+i,d,x);
visited[x]=false;//递归还原条件
}
}
最新文章
- Mac OS、Ubuntu 安装及使用 Consul
- mac电脑http代理服务设置公司内网的相关配置
- 解决word2013图片不能替换
- [.net 面向对象程序设计进阶] (28) 结束语——告别2015
- Volley 实现原理解析(转)
- vbs xml 解析
- RFID读卡器设置卡
- php 未配置curl
- Java学习笔记(1)
- Charles使用问题, iOS7的http代理(http proxy)配置不生效问题
- ios 中介者模式
- javascript利用map,every,filter,some,reduce,sort对数组进行最优化处理
- 【Core2.0帮助类】
- SQLServer 删除表中的重复数据
- video标签 api
- easyui-datagrid个人实例
- Visual Studio使用阿里云Code Git服务器的常见问题
- 【CMS】安装CMS
- Jenkins2.138配置slave节点时,启动方法只有两个选项
- js arguments 内置对象
热门文章
- Winserver+Apache+django部署
- nyoj 寻找最大数
- JAVA_SE基础——51.内部类
- 虚拟机Vmware成功安装Ubuntu Server 16.04中文版
- emqtt 试用(九)ssl认证 - 客户端 mqttfx 验证
- 赛码网算法: 上台阶 ( python3实现 、c实现)
- 在Visual Studio2017和2015中开发报表项目
- [转][scrapy] CannotListenError: Couldn’t listen on [Errno 98] Address already in use.
- else语句的搭配
- poj1182-食物链-带权并查集-种类并查集