POJ1769（线段树+DP)

题意 : 给定一个区间长度 n ，接下来给出 m 个子区间，要求最少选出多少个区间才能使得 1~n 这个区间被所选的所有子区间覆盖

分析：

首先是动态规划，dp[i]表示把最大值从1位置搞到第i个小装置结尾最少需要多少个小装置，这样的话，从小到大遍历所有装置，每次查询当前装置之前的装置区间和当前装置相交的装置，更新dp就可以了。

那么问题就来了，装置有m个，这样O(m^2)的算法绝壁TLE。

用线段树来维护区间最小dp值信息，每个点维护ll到rr范围内的dp最小是多少。没算完一个新的小装置只需把它的dp值插到树上就行了。

然后TLE了，这里有个小贪心，每次更新不需要更新区间信息，因为对每个区间，r点之前的信息对更新之后的装置dp没有贡献，因为要努力使最大值向右移，因此单点更新即可。

AC代码：

#include <cstdio>

#include <algorithm>

#include <string.h>

using namespace std;

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1

const int maxn = 5e4 + ;

const int INF = 0x3f3f3f3f;

int minx[maxn<<];

int dp[maxn];

int L[], R[];

void PushUP(int rt) { minx[rt] = min(minx[rt<<], minx[rt<<|]); }

void build(int l,int r,int rt) {

    if (l == r) {

        minx[rt] = INF;

        return ;

    }

    int m = (l+r)>>;

    build(lson);

    build(rson);

    PushUP(rt);

}

void update(int p,int sc,int l,int r,int rt) {//单点更新，参数(更新点，更新值，总区间左端点，总区间右端点，根节点编号)

    if (l == r) {

        minx[rt] = sc;

        return ;

    }

    int m =(l+r)>>;

    if (p <= m) update(p , sc , lson);

    else update(p , sc , rson);

    PushUP(rt);

}

 int query(int L,int R,int l,int r,int rt) {//查询最大值的写法、最小值同理、求和区间写法在下面

     if (L <= l && r <= R)

         return minx[rt];

     int m = (l + r) >> ;

     int ret = INF;

     if (L <= m) ret = min(ret , query(L , R , lson));

     if (R > m) ret = min(ret , query(L , R , rson));

     return ret;

 }

int main(void)

{

    int m, n;

    scanf("%d %d", &n, &m);

        for(int i=; i<=m; i++)

            scanf("%d %d", &L[i], &R[i]);

        build(, n, );

        for(int i=; i<=n; i++)

            dp[i] = INF;

        dp[] = ;

        update(, , , n, );

        for(int i=; i<=m; i++){

            int val = query(L[i], R[i], , n, ) + ;

            if(val < dp[R[i]]){

                //printf("%d %d\n", L[i], R[i]);

                update(R[i], val, , n, );

                dp[R[i]] = val;

            }

        }

        printf("%d\n", dp[n]);

    return ;

}

巴特西

POJ1769（线段树+DP)

最新文章

热门文章