首页 > 代码库 > FZU 2079 最大获利（线段树+DP）
FZU 2079 最大获利（线段树+DP）
Description
Sean准备投资一些项目。有n个投资项目，投资第i个项目需要花费Ci元。Sean发现如果投资了某些编号连续的项目就能赚得一定的钱。现在给出m组连续的项目和每组能赚得的钱，请问采取最优的投资策略的最大获利是多少？
样例最佳策略是全部项目都投资，然后第1，2组都满足了，获利为2+2-3=1。最佳策略可能是不投资，即最大获利为0。
Input
每组数据第一行输入两个整数N和M , N表示项目数，M表示能获利的连续的项目组数，1 <= N <= 20000,1 <= M <= 20000 , 接下来一行输入N个数，表示每个项目投资需要的花费Ci，1<=Ci<=10^9。
接下来m行，每行3个数Li,Ri,Pi，1<=Li<=Ri<=N,1<=Pi<=10^9,表示投资从第Li到第Ri这些连续的项目的获利。每组连续投资的获利互不影响，如果投资的多组连续投资都包含项目i，项目i只需要投资一次。
Output
对于每组数据输出一行，即最大获利。
Sample Input
3 2
1 1 1
1 2 2
2 3 2
Sample Output
1
设dp[i]表示，前i个项目的最大获利。
转移方程 ： dp[i] = max( dp[i-1] , dp[j-1] + w[j][i] ) , ( 1<=j <=n ).
枚举状态费用O（n） , 用线段树优化取最值，更新费用为O(log n ) , 总复杂度为O（n log n ）。
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <map>#include <set>#include <stack>#include <algorithm>using namespace std;typedef long long LL;const int N = 200010;const int inf = 1e9+7;const double PI = acos(-1.0);const double eps = 1e-6 ;#define root 1,n,1#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define lr rt<<1#define rr rt<<1|1int n , m ;struct node { int l , r , w ; bool operator < ( const node &a ) const { if( r != a.r ) return r < a.r ; else return l > a.l ; }}e[N];LL dp[N] , cost[N] ;void init(){ memset( dp , 0 , sizeof dp );}LL date[N<<2] ,lazy[N<<2];void build( int l , int r , int rt ) { date[rt] = lazy[rt] = 0 ; if( l == r ) return ; int mid = ( l + r ) >> 1 ; build(lson); build(rson);}void Down( int l , int r , int rt ) { if( l == r ) return ; if( lazy[rt] != 0 ) { date[lr]+= lazy[rt] , lazy[lr] += lazy[rt]; date[rr]+= lazy[rt] , lazy[rr] += lazy[rt]; lazy[rt] = 0 ; }}void Up( int rt ) { date[rt] = max( date[lr] , date[rr] ); }void update( int l , int r , int rt , int L , int R , LL val) { if( L == l && r == R ) { date[rt] += val , lazy[rt] += val ; return ; } Down(l,r,rt); int mid = (l+r) >> 1; if( R <= mid ) update(lson,L,R,val); else if( L > mid ) update(rson,L,R,val); else update(lson,L,mid,val) , update(rson,mid+1,R,val); Up(rt);}LL query( int l , int r , int rt , int L , int R ) { if( L == l && r == R ) { return date[rt]; } Down(l,r,rt); int mid = (l+r)>>1; if( R <= mid ) return query(lson,L,R); else if( L > mid ) return query(rson,L,R); else return max( query(lson,L,mid),query(rson,mid+1,R) );}void run () { init() ; build(root); for( int i = 1 ; i <= n ; ++i ){ scanf("%I64d",&cost[i]) ; } for( int i = 0 ; i < m ; ++i ) { scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].w); } sort( e , e + m ); int head = 0 ; for( int i = 1 ; i <= n ; ++i ) { update( root , i , i , dp[i-1] ); update( root , 1 , i , -cost[i] ); while( head < m && e[head].r <= i ) update( root , 1 , e[head].l , e[head].w ) , head++ ; dp[i] = max( dp[i-1] , query( root , 1 , i ) ); } printf("%I64d\n",dp[n]);}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL ios::sync_with_stdio(false); while( ~scanf("%d%d",&n,&m) )run() ;}
FZU 2079 最大获利（线段树+DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。