锐客网

  1. 首页 > it技术 > >

洛谷P1868 饥饿的奶牛【DP】

时空限制 1000ms / 128MB
题目描述 有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。
现用汉语翻译为：
有N个区间，每个区间x，y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。
输入格式： 第一行，N，如题
接下来N行，每行一个数x，y，如题
输出格式： 一个数，最多能吃到的牧草堆数
说明 1<=n<=150000
0<=x<=y<=3000000
题目分析 先将所有草堆以右端点为第一关键字排序
d p [ i ] dp[i] dp[i]表示考虑前 i i i堆草能获得的最大数量
那么有dp转移
d p [ i ] = m a x ( d p [ i ? 1 ] ,R i ? L i + 1 ,m a x ( d p [ j ] + R i ? L i + 1 ) ) ( 1 < = j < i ,R j < L i ) dp[i]=max(dp[i-1],\ R_i-L_i+1,\ max(dp[j]+R_i-L_i+1))(1< =j< i,\ R_j< L_i) dp[i]=max(dp[i?1], Ri??Li?+1, max(dp[j]+Ri??Li?+1))(1<=j 显然 d p [ i ] dp[i] dp[i]一定是不下降的
若不存在 j j j满足 ( 1 < = j < i ,R j < L i ) (1< =j< i,\ R_j< L_i) (1<=j 也就是要么不选第 i i i堆，要么只选第 i i i堆
【洛谷P1868 饥饿的奶牛【DP】】而如果存在这样的 j j j
直接枚举 j j j去更新是 O ( n 2 ) O(n^2) O(n2)的，肯定T
但注意到 d p [ i ] dp[i] dp[i]的不下降性
所以直接二分寻找满足 1 < = j < i 1< =j< i 1<=j

#include #include #include #include #include #include using namespace std; int read() { int f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1; ss=getchar(); } while(ss>='0'&&ss<='9'){x=x*10+ss-'0'; ss=getchar(); } return f*x; }const int maxn=200010; int n; struct node{int ll,rr; }rem[maxn]; bool cmp(node a,node b){return a.rr==b.rr?a.ll>1; if(rem[mid].rr

    推荐阅读


    上一篇：arm-eabi-gdb|arm-eabi-gdb 与 redboot 配合调试 ecos application

    下一篇：高性能查找数组中的最大值和最小值