比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
3
0 2 3
m条直线的交点方案数
=(m-r)条平行线与r条直线交叉的交点数
+ r条直线本身的交点方案
=(m-r)*r+r条之间本身的交点方案数(1<=r<=m)
/*
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
*/
#include<iostream>
using namespace std;
//行数代表几条线,列数代表交点数,当dp[i][j]==1时,代表存在 int dp[][] = {};//N条线最多 n*(n-)/ 2个交点 int main()
{
int N,b;
while(cin>>N)
{
dp[][] = dp[][] = ;//n =0和n = 1的情况
for(int n = ;n<=N;n++) //代表n条线
{
dp[n][] = ; //n条直线都平行时交点为0 for(int i=;i<n;i++)//i表示n条直线有i条平行
{ for(int j=;j<=n*(n-)/;j++)//j表示交点数
{
b = n - i -; //b为n条直线减去平行线
if(dp[b][j] == )
dp[n][(n-b)*b+j] = ;//m条直线的交点方案数 = (m-b)*b+b条之间本身的交点方案数(1<=r<=m) }
}
} for(int j=;j<N*(N-)/;j++)
{
if(dp[N][j] == )
cout<<j<<" ";
}
cout<<N*(N-)/<<endl; }
return ;
}
C++ 计算直线的交点数(动态规划)的更多相关文章
-
HDU-1466 计算直线的交点数 经典dp
1.HDU-1466 计算直线的交点数 2.链接:http://acm.hdu.edu.cn/showproblem.php?pid=1466 3.总结:不会推这个,看了题解.. 状态转移: m条 ...
-
hdu----(1466)计算直线的交点数(dp)
计算直线的交点数 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Su ...
-
HDOJ 1466 计算直线的交点数
将n 条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,......,直线n 和其他n-1条直线最多有n-1个交点.由此得出n条直线互不平行且无三线共点的最多交点数 ...
-
计算直线的交点数(set + 打表)
计算直线的交点数 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total S ...
-
G题 hdu 1466 计算直线的交点数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1466 计算直线的交点数 Time Limit: 2000/1000 MS (Java/Others) ...
-
hdu1466计算直线的交点数 非原创
原文链接 平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数. 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行). Input输入数据包含多个测试实例,每个测试实例占一行,每 ...
-
计算直线的交点数(hdu1466简单的dp)
题意:平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数.比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行). 思路:动态规划,想办法记忆化搜索,当前状态和之前状态结合起来 d ...
-
hdu1466 计算直线的交点数
题意: 平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数. 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行). 分析: DP 设状态:f[i][j]表示i条直线能否产生j个 ...
-
hdu 1466 计算直线的交点数
http://acm.hdu.edu.cn/showproblem.php?pid=1466 N条直线的交点方案数 = c 条直线交叉的交点数与(N-c)条平行线 + c 条直线本身的交点方案 = ( ...
随机推荐
-
B样条基函数的定义和性质
定义:令U={u0,u1,…,um}是一个单调不减的实数序列,即ui≤ui+1,i=0,1,…,m-1.其中,ui称为节点,U称为节点矢量,用Ni,p(u)表示第i个p次(p+1阶)B样条基函数,其定 ...
-
使用phantomjs实现highcharts等报表通过邮件发送(本文仅提供完整解决方案和实现思路,完全照搬不去整理代码无法马上得到效果)
前不久项目组需要将测试相关的质量数据通过每日自动生成报表展示,并自动通过将报表作为邮件正文内容知会到干系人邮箱.那么问题来了,报表生成了,但是邮件怎么发送,因为highcharts等报表都是通过JS和 ...
-
9.1 js基础总结2
3.布尔类型(Boolean) 布尔型数据只有true和false两个值,与字符串不同,不要把布尔值用引号括起来,布尔值false与字符串“false”是两回事. var married = true ...
-
自定义循环滑动的viewpager
今天和大家分享一下如何定制一个可以循环滑动的viewpager.其实今天更重要的提供一种组件化思想,当然你可以理解为面向对象思想. 吐槽一下网上流行的实现方式吧(为了方便说明,下文称之为方式A),方式 ...
-
【wikioi】1041 Car的旅行路线
题目链接 算法:最短路(数据弱,Floyd也能过) 惨痛的教训:此题我至少提交了20次,原因在于= =太草率和粗心了,看到那个多少组数据以为是城市的数量,导致数组开得小小的= =.(对不起,wikio ...
-
mysql已有数据字符集转换
下面模拟把latin1字符集的数据转换为utf8字符集 一.创建测试表和测试数据: 1.修改会话级别的连接字符集 mysql > set names latin1; 查看一下: 2.创建测试表: ...
-
Intellij Idea使用技巧、快捷键
1.Idea设置字体大小:file -> setting -> editor -> colors&font -> save as并自定义 -> font -> ...
-
jquery------显示加载的js时出现中文乱码解决方法
方法: 把my.js文件复制出来,用记事本打开,再另存为的时候设置编码格式为utf-8即可
-
20145305 《Java程序设计》第8周学习总结
教材学习内容总结 1.NIO使用频道来衔接数据节点,可以设定缓冲区容量,在缓冲区中对感兴趣的数据区块进行标记,提供clear().rewind().flip().compact()等高级操作 2.想要 ...
-
Eclipse下建立geoserver源码工程
摘要:本文详细阐述,如何基于geoserver源码构建eclipse工程文件,操作过程中除用到jdk.eclipse以外,还有git和maven,操作系统为windows8. 1安装Git 从(htt ...