Codeforces 437E The Child and Polygon(间隔DP)
2024-08-26 12:36:27
题目链接:Codeforces 437E The Child and Polygon
题目大意:给出一个多边形,问说有多少种切割方法。将多边形切割为多个三角形。
解题思路:首先要理解向量叉积的性质,一開始将给出的点转换成顺时针。然后用区间dp计算。dp[i][j]表示从点i到点j能够有dp[i][j]种分割方法。然后点i和点j能否够做为分割线。要经过推断。即在i和j中选择的话点k的话,点k要在i,j的逆时针方。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 205;
const ll MOD = 1e9+7;
struct point {
ll x, y;
ll operator * (const point& c) const {
return x * c.y - y * c.x;
}
point operator - (const point& c) const {
point u;
u.x = x - c.x;
u.y = y - c.y;
return u;
}
}p[N];
int n;
ll dp[N][N];
void init () {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++)
scanf("%lld %lld", &p[i].x, &p[i].y);
ll tmp = 0;
p[n] = p[0];
for (int i = 0; i < n; i++)
tmp += p[i] * p[i+1];
if (tmp < 0)
reverse(p, p + n);
}
ll solve (int l, int r) {
if (dp[l][r] != -1)
return dp[l][r];
ll& ans = dp[l][r];
ans = 0;
if (r - l == 1)
return ans = 1;
for (int i = l + 1; i < r; i++) {
if ((p[l] - p[r]) * (p[i] - p[r]) > 0)
ans = (ans + solve(l, i) * solve(i, r)) % MOD;
}
return ans;
}
int main () {
init();
printf("%lld\n", solve(0, n-1));
return 0;
}
最新文章
- SQL Server 数据加密功能解析
- SVN更新时,校验和不匹配
- zTree开发下拉树
- vs2013的安装以及单元测试
- 约瑟夫环(Josehpuse)的模拟
- ASP.NET MVC 微信公共平台开发之 微信接入
- 【读书笔记】iOS网络-HTTP-请求内容
- JAVA使用DES加密算法加密解密
- The Trip PC/UVa IDs: 110103/10137, Popularity: B, Success rate: average Level: 1
- Codeforces Round #321 (Div. 2) C. Kefa and Park dfs
- Fiddler 教程(转)
- 如何在myeclipse有个项目文件很多,我想找一段代码,怎么查找?
- linux脚本Shell之九九乘法表
- B. Karen and Coffee
- java参数传递
- python爬取免费优质IP归属地查询接口
- Log4j2配置与使用
- Codeforces 924D Contact ATC (看题解)
- CentOS下iptables详解
- vue1.0到2.0
热门文章
- WebService开启远程测试
- 2-13. 平均两个有序序列(25)(ZJU_PAT 名单 | 排列 )
- Django写的投票系统3(转)
- CF 553A 组合DP
- 2012Android开发热门资料(110个)
- CentOS 如何使用第三方软件库-EPEL与RPMForge、RPMFusion软件库
- cocos2d-html5游戏图片资源选择
- 【Android Training - UserInfo】记住登入用户的信息[Lesson 1 - 使用AccountManager来记住用户]
- 《Javascript高级程序设计》读书笔记之对象创建
- hdu2818行列匹配+排序