DP Codeforces Round #303 (Div. 2) C. Woodcutters

题目传送门

 /*
题意:每棵树给出坐标和高度,可以往左右倒,也可以不倒
问最多能砍到多少棵树
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 ;
}
上一篇:Codeforces Round #323 (Div. 2) Once Again... CodeForces - 582B 最长非下降子序列【dp】(不明白)


下一篇:ubuntu解决网易云无法打开