DP Codeforces Round #303 (Div. 2) C. Woodcutters
2024-08-28 08:33:41
/*
题意:每棵树给出坐标和高度,可以往左右倒,也可以不倒
问最多能砍到多少棵树
DP:dp[i][0/1/2] 表示到了第i棵树时,它倒左或右或不动能倒多少棵树
分情况讨论,若符合就取最大值更新,线性dp,自己做出来了:)
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std; typedef long long LL; const int MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
LL x[MAXN], h[MAXN];
LL dp[MAXN][]; //0-l 1-no 2-r int main(void) //Codeforces Round #303 (Div. 2) C. Woodcutters
{
//freopen ("C.in", "r", stdin); int n;
while (scanf ("%d", &n) == )
{
for (int i=; i<=n; ++i)
{
scanf ("%I64d%I64d", &x[i], &h[i]);
}
memset (dp, , sizeof (dp));
dp[][] = dp[][] = ;
if (x[] + h[] < x[]) dp[][] = ;
for (int i=; i<=n; ++i)
{
LL tmp;
tmp = max (dp[i-][], dp[i-][]);
tmp = max (tmp, dp[i-][]);
dp[i][] = tmp;
if (x[i] - h[i] > x[i-])
{
dp[i][] = max (dp[i-][], dp[i-][]) + ;
}
if (x[i] - x[i-] > h[i-] + h[i])
{
dp[i][] = max (dp[i][], dp[i-][] + );
}
if (i < n && x[i] + h[i] < x[i+])
{
dp[i][] = tmp + ;
}
if (i == n) dp[i][] = tmp + ;
} LL ans;
ans = max (dp[n][], dp[n][]);
ans = max (ans, dp[n][]);
printf ("%I64d\n", ans);
} return ;
}
最新文章
- R自动数据收集第二章HTML笔记1(主要关于handler处理器函数和帮助文档所有示例)
- Angular快速入门篇
- Jsoup开发简单网站客户端之读取本地html文件
- 查询某个表或者所有表的字段说明 SQLServer
- 昂贵的聘礼--POJ1062
- 在后台CS文件里面,隐藏和显示Repeater里面控件
- 树莓派(raspberry)启用root账户 分类: 服务器搭建 Raspberry Pi 2015-04-12 18:45 95人阅读 评论(0) 收藏
- Linux用户及用户组管理
- js 计算两个时间差
- 从客户端检测到有潜在危险的 Reque
- ArcGIS 网络分析[1] 介绍与博文目录【更新中】
- HTML5基本标签的使用
- 关于canvas补充说明
- MySQL 一对多查询
- 剑指offer(21)栈的压入、弹出序列
- MQ与webservice的区别,MQ的区别
- iOS开发 - 事件传递响应链
- 解决ThinkPHP中开启调试模式无法加载模块的问题。
- OK335xS I2C device registe hacking
- 用Spark查询HBase中的表数据
热门文章
- WPF代码注意事项,开发常见问题,知识总结
- 经常使用 Java API
- hihocode #1388 : Periodic Signal NTT
- Mysql性能优化笔记
- CH 5105 Cookies(贪心+DP)
- hihoCoder 1586 Minimum 【线段树】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)
- UILabel与UIFont的用法和属性的一些总结
- Spring Boot 整合Servlet
- POJ 2017 Speed Limit (直叙式的简单模拟 编程题目 动态属性很少,难度小)
- MYSQL学习拓展一:MySQL 存储过程之游标的使用!