HDU-1466 计算直线的交点数 经典dp
2024-10-16 12:12:19
1、HDU-1466 计算直线的交点数
2、链接:http://acm.hdu.edu.cn/showproblem.php?pid=1466
3、总结:不会推这个,看了题解。。
状态转移: m条直线方案数=(m-r)条平行直线与r条直线相交数+r条直线自身方案数
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f int main()
{
int n,dp[][];
memset(dp,,sizeof(dp));
dp[][]=,dp[][]=,dp[][]=; for(int i=;i<;i++){
dp[i][]=;
} for(int m=;m<=;m++){
for(int r=;r<=m;r++){
for(int i=;i<=r*(r-)/;i++){
if(dp[r][i]){ // i为r条直线自身交点数 dp[m][(m-r)*r+i]=;
//(m-r)*r为(m-r)条平行直线与r条直线交点数,(m-r)*r+i即为m条直线交点数
}
}
}
} while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n*(n-)/;i++){
if(dp[n][i]){
printf("%d ",i);
}
}
printf("%d\n",n*(n-)/);
} return ;
}
最新文章
- yum -y upgrade 和 yum -y update 区别
- 理解Java中的final和static关键字
- mysql如何修改所有的definer
- LEARUN 开发框架 /aspnetboilerplate ----上海力软信息技术有限公司
- 应用引擎BAE3.0介绍及百度BAE3.0支持并发多少
- linux 中 ‘|’的作用
- Visual studio 2015程序转Eclipse gun编译出现的问题总结
- html打印表格每页都有的表头和打印分页
- 易pc,1G容量以上的u盘,另外还要一台装了windows系统的电脑。
- Oracle运维 专业的事情交给专业的人来做
- WPF类层次结构
- 如何用PHP遍历文件数目 或删除目录下的全部文件?
- Mybatis-Generator生成Mapper文件中<;if test=";criteria.valid";>;的问题解答
- wincc flexable变量组态
- redis安装、测试&;集群的搭建&;踩过的坑
- web前端开发工程师工资多少
- Java中值传递和引用传递的区别
- gdb 调试 python
- Get Luffy Out * HDU - 1816(2 - sat 妈的 智障)
- 11.DataGrid分页
热门文章
- OCJP(1Z0-851) 模拟题分析(二)over
- LinkedList - java.util.ConcurrentModificationException
- 解决postgresql -- ERROR: 42601: query has no destination for result data
- 团队作业-第二周-SRS文档
- 2-01SQL的概述
- 让用VS2012/VS2013编写的程序在XP中顺利运行
- LaTex学习笔记(一)
- sql修改约束语法练习
- Released Mocked Streams for Apache Kafka
- Java Math floor round ceil 函数