首页    技术博客    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



推荐阅读
  • int

    UNP 第9章：主机名与地址转换

    UNP 第9章：主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]
  • int

    USACO 2014 Jan - Moolympics区间记录优化算法

    题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]
  • utf-8

    分页插件3指定到某一页

    前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]
  • int

    Objective-C 编程中的关键语法点

    本文探讨了 Objective-C 中的一些重要语法特性，包括 goto 语句、块（block）的使用、访问修饰符以及属性管理等。通过实例代码和详细解释，帮助开发者更好地理解和应用这些特性。 ... [详细]
  • int

    Splay Tree 区间操作优化

    Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]
  • int

    深入理解KMP算法中的next数组：北大OJ 2406题解

    本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • int

    使用Objective-C和dispatch库实现并发素数计算

    本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]
  • int

    Java 中 Writer flush()方法，示例

    Java 中 Writer flush()方法，示例 ... [详细]
  • join

    技术分享：从动态网站提取站点密钥的解决方案

    技术分享：从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]
  • require

    网络链路质量监控：Smokeping部署与配置

    本文详细介绍了如何在Linux系统上安装和配置Smokeping，以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装，确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • int

    Java并发编程：LinkedBlockingQueue的实际应用

    本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]
  • int

    深入理解Cookie与Session会话管理

    深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]
  • int

    CentOS7源码编译安装MySQL5.6

    CentOS7源码编译安装MySQL5.6
    2019独角兽企业重金招聘Python工程师标准一、先在cmake官网下个最新的cmake源码包cmake官网：https:www.cmake.org如此时最新 ... [详细]
  • int

    Java面试题解析

    本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • case

    HTML Attribute Naming Conventions for Fast Components

    This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]
author-avatar
咸咸
这个家伙很懒，什么也没留下！
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社区 版权所有