hdn2050(递推之画直线求区域个数)

2024-02-27 11:10

本文主要是介绍hdn2050(递推之画直线求区域个数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=2050

折线分割平面

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19960    Accepted Submission(s): 13696


Problem Description
我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平面分成7部分,具体如下所示。

Input
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0<n<=10000),表示折线的数量。


Output
对于每个测试实例,请输出平面的最大分割数,每个实例的输出占一行。


Sample Input
   
2 1 2

Sample Output
   
2 7


解题思路:1递推递推,先分析下直线分割平面的情况,增加第n条直线的时候,跟之前的直线最多有n-1个交点,此时分出的部分多出了

      (n-1)+1;

     2折线也是同理,f(1)=2,f(2)=7,先画好前面n-1条折线,当增加第n条拆线时,此时与图形新的交点最多有2*2(n-1)个,所以分出的部分多出了2*2(n-1)+1   所以推出f(n)=f(n-1)+4*(n-1)+1,n>=3

#include <stdio.h>
int main()
{__int64 a[100001]={0,2,7};int i,j,k,n,m;while(scanf("%d",&n)!=EOF){while(n--){scanf("%d",&m);if(m>=3){for(i=3;i<=m;i++)a[i]=a[i-1]+4*(i-1)+1;}printf("%I64d\n",a[m]);}}return 0;
}


这篇关于hdn2050(递推之画直线求区域个数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/752199

相关文章

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内,对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序,每个数有两位,每位的取值范围是[0..n-1],再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,

YOLOv8/v10+DeepSORT多目标车辆跟踪(车辆检测/跟踪/车辆计数/测速/禁停区域/绘制进出线/绘制禁停区域/车道车辆统计)

01:YOLOv8 + DeepSort 车辆跟踪 该项目利用YOLOv8作为目标检测模型,DeepSort用于多目标跟踪。YOLOv8负责从视频帧中检测出车辆的位置,而DeepSort则负责关联这些检测结果,从而实现车辆的持续跟踪。这种组合使得系统能够在视频流中准确地识别并跟随特定车辆。 02:YOLOv8 + DeepSort 车辆跟踪 + 任意绘制进出线 在此基础上增加了用户

求空间直线与平面的交点

若直线不与平面平行,将存在交点。如下图所示,已知直线L过点m(m1,m2,m3),且方向向量为VL(v1,v2,v3),平面P过点n(n1,n2,n3),且法线方向向量为VP(vp1,vp2,vp3),求得直线与平面的交点O的坐标(x,y,z): 将直线方程写成参数方程形式,即有: x = m1+ v1 * t y = m2+ v2 * t

LCP 485. 最大连续 1 的个数[lleetcode -11]

从今天起,我们的算法开始研究搜索,首先就是DFS深度优先搜索(depth-first seach,DFS)在搜索到一个新的节点时,立即对该新节点进行遍 历;因此遍历需要用先入后出的栈来实现,也可以通过与栈等价的递归来实现。对于树结构而言, 由于总是对新节点调用遍历,因此看起来是向着“深”的方向前进。 下面是一个一维的DFS算法 LCP 485. 最大连续 1 的个数 给定一个二进制数组 nu

JVM - Java内存区域

文章目录 目录 文章目录 运行时数据区域 程序计数器 栈 Java虚拟机栈 本地方法栈 栈帧的组成 局部变量表 操作数栈 帧数据 堆 方法区 直接内存 总结 运行时数据区域 Java虚拟机在执行Java程序的过程中会把它所管理的内存区域划分为若干个不同的数据区域。这些区域有各自的用途,以及创建和销毁时间,有的区域随着虚拟机进程的启动而一直存在,有的区域则是依赖

Ai+若依(智能售货机运营管理系统---帝可得)-人员管理-点位管理-区域管理-合作商管理----【08篇---0001:上】

项目介绍 售货机简介 帝可得是一个基于物联网概念下的智能售货机运营管理系统 物联网 物联网(IoT:Internet of Things)简单来说,就是让各种物品通过互联网连接起来,实现信息的交换和通信。 这个概念听起来可能有点抽象,但我们可以把它想象成一个超级大的社交网络。不过,这个网络里的成员不是人类,而是各种物品。比如,你的冰箱、洗衣机、甚至是你的汽车,它们都可以通过互联网互