首页 > 其他分享 >codeforces 545C C. Woodcutters(dp+二分)

codeforces 545C C. Woodcutters(dp+二分)

时间:2023-04-23 21:39:37浏览次数:58  
标签:xi int MAX codeforces mid include 545C dp


题目链接:

codeforces 545C


题目大意:

给出一些树的位置和高度,每棵树可以砍倒,覆盖[xi−hi,xi]或者覆盖[xi,xi+hi],或者不砍倒,问最多砍倒多少棵树?


题目分析:

我们记录dp[i]表示选取到i棵树的时候用的最短的区间长度。每次枚举每棵树,二分到最大的不超过当前树位置的个数,然后利用当前树的信息更新dp[i]。如果当前树左倒或者右倒会压到临近的树,那么当前树不能砍。


AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 100007

using namespace std;

int dp[MAX];
int x[MAX];
int h[MAX];
int n;
const int INF = 2e9+7;

int bsearch ( int x )
{
    int l = 0 , r = n , mid;
    while ( l != r )
    {
        mid = (l+r+1)>>1;
        if ( dp[mid] < x ) l=mid;
        else r = mid-1;
    }
    return l;
}

int main ( )
{
    while ( ~scanf ("%d" , &n ))
    {
        for ( int i = 1 ; i <= n ; i++ )
            dp[i] = INF;
        dp[0] = -INF;
        for ( int i = 1 ; i <= n ; i++ )
            scanf ("%d%d" , &x[i] , &h[i] );
        for ( int i = 1 ; i <= n ; i++ )
        {
            int id = bsearch ( x[i] )+1;
            if ( i == n || x[i]+h[i] < x[i+1] )
                dp[id] = min ( dp[id] , x[i]+h[i] );
            id = bsearch ( x[i]-h[i] )+1;
            if ( i == 1 || x[i]-h[i] > x[i-1] )
                dp[id] = min ( dp[id] , x[i] );
        }
        int ans;
        for ( int i = n ; i >= 1 ; i-- )
            if ( dp[i] != INF )
            {
                ans = i;
                break;
            }
        printf ( "%d\n" , ans );
    }
}


标签:xi,int,MAX,codeforces,mid,include,545C,dp
From: https://blog.51cto.com/u_7936627/6218738

相关文章

  • codeforces 4D D. Mysterious Present(dp)
    题目连接:codeforces4D题目大意:给出n个信封,这n个信封有长和宽,给出卡片的尺寸,求取能够装入卡片的最长的序列,序列满足后一个的长和宽一定大于前一个,求最长的这个序列的长度,并且给出一组可行解。题目分析:一看这种题目就是dp的题目,状态定义dp[i]为以i结尾的序列的最大的长度,并且利用一......
  • codeforces 2B B. The least round way(dp+数论)
    题目链接:codeforces2B题目大意:给出一个n*n的矩阵,从左上角走到右下角,只能向右或向下走,问路径上的数之积末尾0最少的方案是什么。题目分析:首先我们要做两个预处理,处理出每个位置上的数包含多少个2的质因子和多少个5这个质因子然后我们统计路径上弄到最少的2的方案数和最少的5的方案......
  • codeforces 126B B. Password(kmp+dp)
    题目链接:codeforces126B题目大意:给出一个字符串,找出一个子串既是它的前缀,也是它的后缀,还是一个非后缀也非前缀的子串。题目分析:本来挺简单的一个题,最开始想复杂了,还用了后缀数组,醉了。这个题主要用的是kmp的next数组,首先我们要了解next数组的定义,next[i]表示以i为末尾的子串的后缀......
  • codeforces 118D D. Caesar's Legions(dp)
    题目链接:codeforces118D题目大意:给出n1个1,n2个2,给出k1和k2代表连续的1和2的最大长度,问能够构造的合法的不同串的数量。题目分析:能够递推,所以想到能够利用dp做。首先我们定义状态,dp[i][j][k][2]代表以1或2结尾,结尾相同的元素的数量为k,1的总数是j的当前序列长度为i的串的数量。首先......
  • codeforces 264B B. Good Sequences(dp+数论)
    题目链接:codeforces264B题目大意:给出n个数,利用这n个数构造一个好的序列,好的序列是单调增的,而且序列中相邻的两个元素都不互质,问最长的好序列的长度是多少。题目分析:首先我们定义状态dp[i]表示当前的数进行构造的序列末尾的数的质因数包含i的时候的最长的情况。然后我们从小到大枚......
  • codeforces 159D D. Palindrome pairs( manacher+dp )
    题目链接:codeforces159D题目大意:给出一个字符出,求取这个字符串中互相不覆盖的两个回文子串的对数。题目分析:首先能够用manacher模板,因为这个算法处理的字符串的长度式奇数,所以我们首先将原字符串拓展,也就是用一个没有出现过的子串填充到每两个字符之间,首位也要添加,这样处理后得到......
  • codeforces 359B B. Permutation(简单构造)
    题目链接:codeforces359B题目大意:给出n和k,要求构造一个长度为2*n的排列,满足如下的式子:∑i=1n|a2∗i−1−a2∗i|−|∑i=1na2∗i−1−a2∗i|=2∗k题目分析:首先最终构造的2*k一定是小于n的偶数,如果我们直接放入自然数的排列,结果是0,我们将2*i-1和2*i分为一组,每次调换组内位置(每组只能......
  • codeforces 505B B. Mr. Kitayuta's Colorful Graph(bfs)
    题目链接:codeforces505B题目大意:给出一个有向图,边有不同的颜色,任意给出查询,查询两点能够只通过一种颜色连通的颜色的种类数。题目分析:根据不同颜色建边,bfs即可,队列维护可用的点。AC代码:#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<alg......
  • codeforces 332B B. Maximum Absurdity(rmq)
    题目链接:codeforces332B题目大意:给出一个序列,让找出不互相覆盖的两个长度为k的段,问在两个段的权值和最大的情况下,按照左边段的左端点排序,右边段的左端点作为第二关键字排序,得到的第一个答案。题目分析:很水的数据结构的题目,我们只需要先利用前缀和预处理出所有长度为k的段的总权值......
  • codeforces 234C C. Weather(枚举+前缀后缀预处理)
    题目链接:codeforces234C题目大意:给出一个序列,问最少修改多少个元素,能保证前半截全是负数,后半截全是正数。题目分析:预处理出前缀中大于等于0的数的个数和后缀中小于等于0的数的个数。枚举每一个位置,判断以当前位置为分界点时需要修改的元素的个数。AC代码:#include<iostream>#inc......