思路:

记忆化搜索。

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 ;
}

最新文章

  1. android app自动化测试之UIAutomator
  2. fedora各个版本的下载地址archive
  3. hibernate 表配置文件如何设置表字段的默认值
  4. poj1129 Channel Allocation(染色问题)
  5. 【M5】对定制的“类型转换函数”保持警觉
  6. UIPickerView 创建中国地区显示 省份 市
  7. zoj 1649 Rescue
  8. h5前端流行的框架
  9. 学习css之选择器优先级
  10. ruby如何查找一个方法属于哪个类
  11. python 加密算法及其相关模块的学习(hashlib,random,string,math)
  12. struts配置文件说明
  13. 深入学习semaphore
  14. IE7下onclick事件失效的问题
  15. Finalize方法的生成
  16. Getting Started with Processing 第四章总结
  17. C++进阶小结
  18. 数组新增,修改json数据
  19. 在 mvc 4 中使用 unity 进行依赖注入
  20. ubuntu init启动流程

热门文章

  1. Git回退---reset和revert
  2. easyui webuploader 文件上传演示
  3. CentOS 6.9正式版下载
  4. Lightoj 1027 - A Dangerous Maze 【期望】
  5. ubuntu语言设置成汉语
  6. [GraphQL] Query Local and Remote Data in Apollo Link State
  7. Java RMI之HelloWorld程序以及相关的安全管理器的知识
  8. JSP简单练习-包装类综合应用实例
  9. jq 常用手册
  10. web container和spring container之间的关系