[FJWC2019 Day1] 全连
时间限制：1000MS 内存限制：262144KB
难度： 4.5
给定两个长度为 n 的序列 a 和 t，可以在其中选择一些元素构成集合 S ，使得 \sum\limits_{i \in S}{a_i \times t_i} 最大。
同时，集合 S 还要满足 \forall i \in S, \forall j \in (i-t_i, i+t_i) ， j \notin S 。
第一行一个整数 n ；
第二行 n 个整数表示序列 t ；
第三行 n 个整数表示序列 a 。
一行一个整数，即答案。
S=\{1,3,5\}，答案 =2 \times 3 + 2 \times 2 + 2 \times 4 = 18 。
保证 t_i \leq n ， a_i \leq 10^9 ，1 \leq n \leq 10^6 。
YZOJ P4257, YZOJ P3993
其实是大水题，但是我这么简单的DP方程都没想清楚直接快乐爆零。
可以发现，只要 S 中相邻最近的两个元素满足条件就可以了。所以设 f_i 为 前 i 个中元素中，选择第 i 个元素的最大答案。
所以显然 f_i = \max \limits _ {j + t_j \le i \land j \le i – t_i}{f_j + t_i \times a_i} ，答案就是 \max\limits_i{f_i} 。
然后这是一个裸的二维偏序，即贡献有两个条件 j+t_j \leq i 和 j \leq i-t_i 。最常见做法的是把一维拿去排序，剩下一维拿数据结构维护。在这里，把 j+t_j 拿去排序，然后维护 i-t_i 的树状数组，时间复杂度就是 O(nlogn) 。
（因为我比较菜，一直在纠结贡献的顺序即 i>j ，所以在这里说明一下：首先 j+t_j 排完序后就是单调的，对于当前元素 i 就可以快速找出哪些元素是可以可以对其产生贡献的。又 i 也是单调的，始终满足 j+t_j \leq i ，所以这个元素都可能对 i 后的元素产生贡献，就把它加入树状数组。那么对于当前元素 i ，要对它产生贡献只剩下 j \leq i-t_i 这一个条件了。因为树状数组维护区间 [1, o] 的特性，所以加入树状数组的时候把节点编号和其对应 f 加进去，查询 i-t_i 即可。特别注意，这里的贡献仍然是顺序的！不要像我一样犯傻，因为随着 i 的增加才会有更多的 j+t_j \leq i 满足！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } struct _node { int v,idx; bool operator < (const _node&o)const { return v<o.v; } }seg[1050505]; int N; int t[1050505],a[1050505]; long long f[1050505],fsg[1050505]; #define _lowbit(_o_) ((_o_)&-(_o_)) inline void update(register int o,const long long&val) { while(o<=N) { fsg[o]=_max(fsg[o],val); o+=_lowbit(o); } } inline long long query(register int o) { long long ans=0; while(o) { ans=_max(ans,fsg[o]); o-=_lowbit(o); } return ans; } int main() { //freopen("fc.in","r",stdin);freopen("fc.out","w",stdout); N=getnum(); for(register int i=1;i<=N;i++) t[i]=getnum(),seg[i].idx=i,seg[i].v=t[i]+i; for(register int i=1;i<=N;i++) a[i]=getnum(); std::sort(&seg[1],&seg[N+1]); register int j=1; long long ans=0; for(register int i=1;i<=N;i++) { long long tpans=0; /*for(register int j=0;j<i;j++) if((i>=j+t[j]) && (j<=i-t[i])) tpans=_max(tpans,f[j]);*/ while(j<=N && seg[j].v<=i) update(seg[j].idx,f[seg[j].idx]),j++; if(i-t[i]>=1) tpans=query(i-t[i]); f[i]=tpans+(long long)t[i]*a[i]; ans=_max(ans,f[i]); } printf("%lld\n",ans); return 0; } |