1 <PRE class=cpp minmax_bound="true">dp+線段樹，包含懶操作</PRE>
view sourceprint?01 #include <iostream>
02 #include <cstdio>
03 #include <memory.h>
04 #include <algorithm>
05 #include <cmath>
06 #include <string>
07 #include <climits>
08 using namespace std;
09 #define N 50003
10 #define INF 1LL*INT_MAX*INT_MAX
11 #define lson rt<<1
12 #define rson rt<<1|1
13
14 struct node
15 {
16 int l,r,lazy;
17 long long num;
18 }st[4*N];
19 long long dp[N],p[N],t[N],lazy[4*N];
20 int n;
21
22 /*void pushup(int rt)
23 {
24 if (st[lson].num==st[rson].num) st[rt].num=st[lson].num;
25 }*/
26 void pushdown(int rt)
27 {
28 if (st[rt].lazy)
29 {
30 st[lson].lazy=1;
31 st[rson].lazy=1;
32 st[lson].num=min(st[rt].num,st[lson].num);
33 st[rson].num=min(st[rt].num,st[rson].num);
34 st[rt].lazy=0;
35 }
36 }
37 void build(int rt,int l,int r)
38 {
39 st[rt].l=l;
40 st[rt].r=r;
41 st[rt].lazy=0;
42 st[rt].num=INF;
43 if (l==r) return;
44 int mid=(l+r)>>1;
45 build(lson,l,mid);
46 build(rson,mid+1,r);
47 }
48 void update(int rt,int l,int r,long long v)
49 {
50 if (l<=st[rt].l && st[rt].r<=r)
51 {
52 st[rt].num=min(st[rt].num,v);
53 st[rt].lazy=1;
54 return;
55 }
56 pushdown(rt);
57 int mid=(st[rt].l+st[rt].r)>>1;
58 if (l<=mid) update(lson,l,r,v);
59 if (r>mid) update(rson,l,r,v);
60 //pushup(rt);
61 }
62 long long query(int rt,int pos)
63 {
64 if (pos==0) return 0;
65 if (st[rt].l==st[rt].r) return st[rt].num;
66 pushdown(rt);
67 int mid=(st[rt].l+st[rt].r)>>1;
68 if (pos<=mid) return query(lson,pos);
69 else return query(rson,pos);
70 }
71 int main()
72 {
73 while (scanf("%d",&n)!=EOF)
74 {
75 for (int i=1;i<=n;i++)
76 scanf("%lld",&p[i]);
77 for (int i=1;i<=n;i++)
78 scanf("%lld",&t[i]);
79 build(1,1,n);
80
81 for (int i=1;i<=n;i++)
82 {
83 long long tmp=query(1,i-1);
84 update(1,i,i+t[i]-1,tmp+p[i]);
85 }
86 printf("%lld\n",query(1,n));
87 }
88 return 0;
89 }
