题意:过每个等级要花费一定能量,部分等级可以买能量,买的能量不可累加,问过完所有等级,最小花费;
思路:dp+线段树维护
dp方程:if(sum【i-1】<=sum【j-1】+powj)dp【i】=min(dp【j】+cost【j】)
那你发现i和j是完全分开的,那么就用线段树去维护一下dp【j】+cost【j】就行了,复杂度nlogn
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1e5+10; const LL INF=0x3f3f3f3f; int n,m; LL sum[maxn],s_pow[maxn],dp[maxn],Min[maxn<<2];; bool vis[maxn]; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 struct shop { int l;LL s,c; shop(int _l=0,LL _s=0,LL _c=0):l(_l),s(_s),c(_c){} bool operator <(const shop &r)const{return l<r.l;} }sh[maxn]; void PushUP(int rt) { Min[rt] = min(Min[rt<<1] , Min[rt<<1|1]); } void build(int l,int r,int rt) { if (l == r) { Min[rt]=INF; return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt); } void update(int p,int sc,int l,int r,int rt) { if (l == r) { Min[rt] = sc; return ; } int m = (l + r) >> 1; if (p <= m) update(p , sc , lson); else update(p , sc , rson); PushUP(rt); } LL query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return Min[rt]; } int m = (l + r) >> 1; LL 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() { while(scanf("%d%d",&n,&m)!=EOF) { memset(sum,0,(n+10)*sizeof(LL)); memset(s_pow,0,(n+10)*sizeof(LL)); memset(dp,0x3f,(n+10)*sizeof(LL)); memset(vis,0,(n+10)*sizeof(LL)); for(int i=1;i<=n;i++) { LL t; scanf("%I64d",&t); sum[i]=sum[i-1]+t; } for(int i=0;i<m;i++) { int l; LL s,c; scanf("%d%I64d%I64d",&l,&s,&c); sh[i]=shop(l,s,c); s_pow[i]=sum[l-1]+s; } sort(s_pow,s_pow+m); sort(sh,sh+m); build(0,m-1,1); dp[1]=0; for(int i=0;i<m;i++) { int l=sh[i].l;LL s=sh[i].s,c=sh[i].c; if(l==1) { int tn=lower_bound(s_pow,s_pow+m,sum[l-1]+s)-s_pow; while(vis[tn]&&tn<m)tn++; update(tn,dp[l]+c,0,m-1,1); vis[tn]=1; } else { int tn=lower_bound(s_pow,s_pow+m,sum[l-1])-s_pow; dp[l]=query(tn,m-1,0,m-1,1); tn=lower_bound(s_pow,s_pow+m,sum[l-1]+s)-s_pow; while(vis[tn]&&tn<m)tn++; update(tn,dp[l]+c,0,m-1,1); vis[tn]=1; } } int tn=lower_bound(s_pow,s_pow+m,sum[n])-s_pow; dp[n+1]=query(tn,m-1,0,m-1,1); printf("%I64d ",dp[n+1]==INF?(LL)-1:dp[n+1]); } return 0; }