首页技术博客 PHP教程数据库技术前端开发 HTML5 Nginx php论坛

新用户注册 | 会员登录

热门标签 | HotTags

当前位置: 开发笔记 > 编程语言 > 正文

3357:[Usaco2004]等差数列

作者：咸咸 | 来源：互联网 | 2024-09-29 09:37

3357:[Usaco2004]等差数列TimeLimit:10SecMemoryLimit:128MBSubmit:321Solved:153[Submit][Status][D

3357: [Usaco2004]等差数列

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 321 Solved: 153
[Submit][Status][Discuss]

Description

约翰发现奶牛经常排成等差数列的号码&＃xff0e;他看到五头牛排成这样的序号&＃xff1a;“1&＃xff0c;4&＃xff0c;3&＃xff0c;5&＃xff0c;7”

很容易看出“1&＃xff0c;3&＃xff0c;5&＃xff0c;7”是等差数列&＃xff0e;

给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9)&＃xff0c;找出最长的等差数列&＃xff0c;输出长度&＃xff0e;

Input

第1行&＃xff1a;一个整数N.

第2到N&＃43;1行&＃xff1a;每行一个整数Ai&＃xff0c;表示牛的号码&＃xff0e;

Output

最长等差数列的长度&＃xff0e;

Sample Input

5
1
4
3
5
7

Sample Output

4

HINT

Source

Green

//f[i][j]表示当前等差数列最后一个数为a[i]&＃xff0c;倒数第二个数为j的最长长度
#include
#include
using namespace std;
int read(){register int x&＃61;0;bool f&＃61;1;register char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;0;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}return f?x:-x;
}
const int N&＃61;1e5&＃43;10;
map<int,int>f[N];
int n,ans,a[N];
int main(){n&＃61;read();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) a[i]&＃61;read();if(n&＃61;&＃61;1){puts("1");return 0;}for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j){ans&＃61;max(ans,f[i][a[j]]&＃61;max(2,max(f[i][a[j]],f[j][2*a[j]-a[i]]&＃43;1)));//这里是等差中项
}}printf("%d",ans);return 0;
}

转:https://www.cnblogs.com/shenben/p/6254890.html

推荐阅读

include
[二分图]JZOJ 4612 游戏

DescriptionInputOutputSampleInput44#****#****#*xxx#SampleOutput5DataConstraint分析非常眼熟࿰ ... [详细]

蜡笔小新 2024-09-28 18:03:01
include
GradeBook类怎么定义

这篇文章主要讲解了“GradeBook类怎么定义”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Grad ... [详细]

蜡笔小新 2024-09-28 08:26:33
include
B查找最大元素（5）

对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串“(max)”。Input输入数据包括多个测试实例，每个实例由一行长度 ... [详细]

蜡笔小新 2024-09-29 10:37:10
include
Matlab中利用mex编译Opencv实现画板绘图功能

图形绘制是标记和可视化数据的重要方法.通过在Matlab中集成画板绘图功能,可为科学计算提供便利.1设置Matlab支持Opencv编译操作系统:麒麟14.04(基于Ubu ... [详细]

蜡笔小新 2024-09-28 11:01:26
include
PATA1121题解

水题。。main.cppPATA1121CreatedbyPhoenixon2018224.Copyright©2018年Phoenix.Allrightsreserve ... [详细]

蜡笔小新 2024-09-28 08:33:52
include
socket8 [命名管道]

::命名管道不但能实现同一台机器上两个进程通信，还能在网络中不同机器上的两个进程之间的通信机制。与邮槽不同，命名管道是采用基于连接并且可靠的传输方式，所以命名管道传输数据只能一对一 ... [详细]

蜡笔小新 2024-09-27 17:36:49
include
HDU-5284-wyh2000 and a string problem(BestCoder Round #48 ($))

wyh2000andastringproblemTimeLimit:20001000MS(JavaOthers)MemoryLimit:13107265 ... [详细]

蜡笔小新 2024-09-27 15:22:22
include
Google 单元测试框架

编译lib手动编译cmake编译gtest测试程序断言和caseFixture使用gmock编译gmock测试程序参考GtestGithub使用gtest(gmock)方便我们编写 ... [详细]

蜡笔小新 2024-09-27 13:27:28
include
BZOJ 3160: 万径人踪灭

FFT+Manacher. ... [详细]

蜡笔小新 2024-09-28 18:40:27
include
Educational Codeforces Round 43 (Rated for Div. 2)

EducationalCodeforcesRound43(RatedforDiv.2)https:codeforces.comcontest976A ... [详细]

蜡笔小新 2024-09-28 14:07:52
include
如何使用C语言strcmp函数

这篇文章将为大家详细讲解有关如何使用C语言strcmp函数，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一 ... [详细]

蜡笔小新 2024-09-28 12:35:27
include
自己动手写下载器简单socket编程

下载器，就是一种网络工具，从网络中接收自己想要的数据。下载器是一个网络客户端。它的下载流程无非就是客户端连接服务器端，然后发送资源下载请求 ... [详细]

蜡笔小新 2024-09-28 11:59:38
include
C++使用临时文件

使用临时文件tmpnam该函数的功能是产生一个唯一的文件名系统回味该文件分配一块内存来保存临时变量例如下面的代码#includeintmain(){charnam ... [详细]

蜡笔小新 2024-09-28 10:56:45
include
【第7周项目4字符串加密】

*Copyright(c)2016,烟台大学计算机与控制工程学院Allrightsreserved.文件名称：字符串加密.cpp作者：彭友程完成日期&# ... [详细]

蜡笔小新 2024-09-27 22:14:40
include
[hdu] 5696 区间的价值 || 序列分治

原题我们定义“区间的价值”为一段区间的最大值*最小值。一个区间左端点在L，右端点在R，那么该区间的长度为(R−L+1)。求长度分别为1～n的区间的最大价值。保证数据随机因为保证数据随 ... [详细]

蜡笔小新 2024-09-27 22:04:53

咸咸

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章

PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved |

京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区版权所有