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



推荐阅读
  • main

    最小路径覆盖与强连通分量的应用：国王的问题

    本题探讨了在一个有向图中，如何根据特定规则将城市划分为若干个区域，使得每个区域内的城市之间能够相互到达，并且划分的区域数量最少。题目提供了时间限制和内存限制，要求在给定的城市和道路信息下，计算出最少需要划分的区域数量。 ... [详细]
  • main

    编程挑战：2019 Nitacm 校赛 D 题 - 雷顿女士与分队（高级版）

    编程挑战：2019 Nitacm 校赛 D 题 - 雷顿女士与分队（高级版）
    本文深入解析了2019年Nitacm校赛D题——雷顿女士与分队（高级版），详细介绍了问题背景、解题思路及优化方案。 ... [详细]
  • default

    CentOS系统安装与配置常见问题及解决方案

    CentOS系统安装与配置常见问题及解决方案
    本文详细介绍了在CentOS系统安装过程中遇到的常见问题及其解决方案，包括Vi编辑器的操作、图形界面的安装、网络连接故障排除等。通过本文，读者可以更好地理解和解决这些常见问题。 ... [详细]
  • uri

    HTTP请求与响应机制详解

    本文深入探讨了HTTP请求和响应对象的使用，详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外，还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]
  • uri

    PHP 过滤器详解

    PHP 过滤器详解
    本文深入探讨了 PHP 中的过滤器机制，包括常见的 $_SERVER 变量、filter_has_var() 函数、filter_id() 函数、filter_input() 函数及其数组形式、filter_list() 函数以及 filter_var() 和其数组形式。同时，详细介绍了各种过滤器的用途和用法。 ... [详细]
  • stream

    Servlet 表单处理：GET 和 POST 请求的深入解析

    本文详细探讨了HTML表单中GET和POST请求的区别，包括它们的工作原理、数据传输方式、安全性及适用场景。同时，通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]
  • char

    如何高效清空C++标准输入缓冲区

    本文探讨了在C++中如何有效地清空输入缓冲区，确保程序只处理最近的输入并丢弃多余的输入。我们将介绍一种不阻塞的方法，并提供一个具体的实现方案。 ... [详细]
  • main

    递推算法与大数处理

    本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数，并使用递推算法和大数处理技术来解决这一问题。 ... [详细]
  • char

    JavaScript 基础语法指南

    JavaScript 基础语法指南
    本文详细介绍了 JavaScript 的基础语法，包括变量、数据类型、运算符、语句和函数等内容，旨在为初学者提供全面的入门指导。 ... [详细]
  • char

    Python处理Word文档的高效技巧

    Python处理Word文档的高效技巧
    本文详细介绍了如何使用Python处理Word文档，涵盖从基础操作到高级功能的各种技巧。我们将探讨如何生成文档、定义样式、提取表格数据以及处理超链接和图片等内容。 ... [详细]
  • byte

    开发笔记:2020 BJDCTF Re encode

    开发笔记:2020 BJDCTF Re encode
    开发笔记:2020 BJDCTF Re encode ... [详细]
  • char

    Linux 文件输入输出操作

    本文介绍了Linux系统中的文件IO操作，包括文件描述符、基本文件操作函数以及目录操作。详细解释了各个函数的参数和返回值，并提供了代码示例。 ... [详细]
  • char

    构建个人博客站点：基于LAMP环境的WordPress部署指南

    本文详细介绍如何利用已搭建的LAMP（Linux、Apache、MySQL、PHP）环境，快速创建一个基于WordPress的内容管理系统（CMS）。WordPress是一款流行的开源博客平台，适用于个人或小型团队使用。 ... [详细]
  • object

    理解反向投影技术及其应用

    反向投影技术主要用于在大型输入图像中定位特定的小型模板图像。通过直方图对比，它能够识别出最匹配的区域或点，从而确定模板图像在输入图像中的位置。 ... [详细]
  • char

    树链问题的优化解法：深度优先搜索与质因数分解

    树链问题的优化解法：深度优先搜索与质因数分解
    本文介绍了一种通过深度优先搜索（DFS）和质因数分解来解决最长树链问题的方法。我们通过枚举树链上的最大公约数（GCD），将所有节点按其质因子分类，并计算每个类别的最长链，最终求得全局最长链。 ... [详细]
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社区 版权所有