首页 > 代码库 > Polygon Division
Polygon Division
题目链接
- 题意:
给一个n边形,求将这个多边形分成只含有三角形和四边形的分割数 - 分析:
太弱了,最开始一直找不到好的状态转移,总是会出现重复,最后还是看的白书得到的启发:
先说一下白书的题目,类似的背景,但是分割只允许分割成三角形。做法是:以某一边形成三角形,来将原图形分割成两个图形,这样转移是不会出现重复的,很好的转移方式……
对于这个题目,一个关键的问题在于能得到四边形,而四边形的转移是不能用上边的方法的。现在就是需要求,当前图形如果含有四边形怎么转移:四边形必定有一边是多边形的边,不妨设某一边就是四边形的边,那么,当前边形成的三角形在加上一个三角形就可以构成一个四边形了(以当前形成的三角形的左腰作为左侧图形的底边来形成三角形,两个三角形就可以组成一个四边形)。那么,递推的时候就需要两个数组,f[i]表示i边形分割成三角形和四边形的个数,g[i]表示将i边形分割后必须以某一边为底边,形成三角形后,之后的随意(四边形、三角形) - 关键:
找到合适的状态转移
四边形分成两个三角形表示
const int maxn = 5100; ULL g[maxn], f[maxn]; void init() { g[2] = 1; f[2] = 1; FF(i, 3, maxn) { int sum = i + 1; FE(j, 2, i - 1) g[i] += f[j] * f[sum - j]; FE(j, 3, i - 1) f[i] += g[j] * f[sum - j]; f[i] += g[i]; } } int main() { init(); int n; while (~RI(n)) { cout << f[n] << endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。