题目传送门

 /*
题意:每棵树给出坐标和高度,可以往左右倒,也可以不倒
问最多能砍到多少棵树
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 ;
}

最新文章

  1. R自动数据收集第二章HTML笔记1(主要关于handler处理器函数和帮助文档所有示例)
  2. Angular快速入门篇
  3. Jsoup开发简单网站客户端之读取本地html文件
  4. 查询某个表或者所有表的字段说明 SQLServer
  5. 昂贵的聘礼--POJ1062
  6. 在后台CS文件里面,隐藏和显示Repeater里面控件
  7. 树莓派(raspberry)启用root账户 分类: 服务器搭建 Raspberry Pi 2015-04-12 18:45 95人阅读 评论(0) 收藏
  8. Linux用户及用户组管理
  9. js 计算两个时间差
  10. 从客户端检测到有潜在危险的 Reque
  11. ArcGIS 网络分析[1] 介绍与博文目录【更新中】
  12. HTML5基本标签的使用
  13. 关于canvas补充说明
  14. MySQL 一对多查询
  15. 剑指offer(21)栈的压入、弹出序列
  16. MQ与webservice的区别,MQ的区别
  17. iOS开发 - 事件传递响应链
  18. 解决ThinkPHP中开启调试模式无法加载模块的问题。
  19. OK335xS I2C device registe hacking
  20. 用Spark查询HBase中的表数据

热门文章

  1. WPF代码注意事项,开发常见问题,知识总结
  2. 经常使用 Java API
  3. hihocode #1388 : Periodic Signal NTT
  4. Mysql性能优化笔记
  5. CH 5105 Cookies(贪心+DP)
  6. hihoCoder 1586 Minimum 【线段树】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)
  7. UILabel与UIFont的用法和属性的一些总结
  8. Spring Boot 整合Servlet
  9. POJ 2017 Speed Limit (直叙式的简单模拟 编程题目 动态属性很少,难度小)
  10. MYSQL学习拓展一:MySQL 存储过程之游标的使用!