首先自我检讨一下,最近忙一些杂事导致OJ与红宝进度严重滞后,今后要学会专注,回避一些不必要的事情。
为了准备12日的校赛做了这题,动态规划,在网上看到的很经典的解法摘录如下:
l题目分析:
将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1和直线2最多有两个交点......直线n和其他n-1条直线最多有n-1个交点,由此得出n条直线互不平行且无三线共点的最多交点数:
max=1+2+...+(n-1)=n(n-1)/2;
设数组
g[1..max],g[i]=0;//交点数i不存在
g[i]=1;//交点数i存在(0<=i<=max)
m条直线的交点方案数=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案=(m-r)*r+r条之间本身的交点方案(1<=r<=m)
上式说明,计算不同交点方案的问题是可以递归的,可描述成如下算法
void F(int m,int j) //m为直线,j为交点数
{
if(m>0)//若直线存在,则递归计算所有的交叉情况
for(int r=m;r>=1;r--)
F(m-r,j+r*(m-r));
else
g[j]=1;
}//确定n条直线存在j个交点
有了上述递归程序后,便可以通过下述方法计算和输出n条直线的交点方案
1.计算max=n*(n-1)/2计算最多交点数
2.初始化数组g
3.递归求g[i]:F(n,0)
4.输出
分享到:
相关推荐
动态规划DP题解 POJ HDU部分动态规划DP题解
关于hdu的动态规划的题目,包括一些水题,还有一些经典的动态规划题目。
HDU 动态规划(46道题目
hdu动态规划算法集锦
HDU的一题........HDU DP动态规
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
杭电ACM课件2014版之 (HDUACM201403版_05)动态规划
HDU动态规划,此PPT系杭州电子科技大学ACM总教练刘春英老师所有, 特在此分享贡献给广大编程爱好者, 特别是ACMer!
动态规划DP题解 POJ HDU 动态规划解题报告
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
这是一个相当齐全的算法课件 里面包含了很多的内容和实例 使我们上课时老师的课件 希望对大家有帮助
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...