poj1923 Fourier's Lines
2024-08-30 06:41:36
思路:
记忆化搜索。
n条直线的交点方案数
=(n-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案
=(n-r)*r+r条直线之间本身的交点方案数(0<r<=n)
于是可以枚举r,递归来计算。
实现:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int dp[][];
int dfs(int n, int m)
{
if (m < || m > n * (n - ) >> ) return ;
if (!m) return ;
if (dp[n][m] != -) return dp[n][m];
for (int i = ; i <= n; i++)
{
if (dfs(n - i, m - i * (n - i)))
return dp[n][m] = ;
}
return dp[n][m] = ;
} int main()
{
int kase = , n, m;
memset(dp, -, sizeof(dp));
while (cin >> n >> m, n + m)
{
if (dfs(n, m))
cout << "Case " << kase++ << ": " << n << " lines with exactly " << m << " crossings can cut the plane into " << n + m + << " pieces at most." << endl;
else
cout << "Case " << kase++ << ": " << n << " lines cannot make exactly " << m << " crossings." << endl;
}
return ;
}
最新文章
- android app自动化测试之UIAutomator
- fedora各个版本的下载地址archive
- hibernate 表配置文件如何设置表字段的默认值
- poj1129 Channel Allocation(染色问题)
- 【M5】对定制的“类型转换函数”保持警觉
- UIPickerView 创建中国地区显示 省份 市
- zoj 1649 Rescue
- h5前端流行的框架
- 学习css之选择器优先级
- ruby如何查找一个方法属于哪个类
- python 加密算法及其相关模块的学习(hashlib,random,string,math)
- struts配置文件说明
- 深入学习semaphore
- IE7下onclick事件失效的问题
- Finalize方法的生成
- Getting Started with Processing 第四章总结
- C++进阶小结
- 数组新增,修改json数据
- 在 mvc 4 中使用 unity 进行依赖注入
- ubuntu init启动流程