首页 > 代码库 > Bzoj3747 [POI1015] Kinoman
Bzoj3747 [POI1015] Kinoman
Description
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
Input
第一行两个整数n,m(1<=m<=n<=1000000)。
第二行包含n个整数f[1],f[2],…,f[n](1<=f[i]<=m)。
第三行包含m个整数w[1],w[2],…,w[m](1<=w[j]<=1000000)。
Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。
Sample Input
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
2 3 1 1 4 1 2 4 1
5 3 6 6
Sample Output
15
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
Bzoj权限题。只过了样例，尚未评测。
题面搬运自神犇hzwer博客。
线段树维护区间最值，枚举区间起点，不断把起点前面的电影贡献值删去，再把当前电影“从当前直到它下次出现之前”的区间都新加上当前电影的贡献值，不断更新最大答案。
刚开始按区间加法写的，所以变量用了sum，写到一半发现只搞区间最大值就好，然而懒得改变量名了……
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define ls l,mid,rt<<1 7 #define rs mid+1,r,rt<<1|1 8 #define LL long long 9 using namespace std;10 const int mxn=1000010;11 int n,m;12 int f[mxn],w[mxn];13 int next[mxn],last[mxn];14 int cnt[mxn];15 struct node{16 LL sum;//变量名是sum，实际是存区间最大值 17 LL tag;18 }t[mxn<<2];19 void Build(int l,int r,int rt){//init //实际并没有用到 20 if(l==r){21 t[rt].sum=t[rt].tag=0;22 return;23 }24 int mid=(l+r)>>1;25 Build(ls);Build(rs);26 return;27 }28 void pushdown(int l,int r,int rt){29 if(l==r)return;30 if(t[rt].tag){ 31 int mid=(l+r)>>1;32 t[rt<<1].tag+=t[rt].tag;33 t[rt<<1|1].tag+=t[rt].tag;34 t[rt<<1].sum+=t[rt].tag;35 t[rt<<1|1].sum+=t[rt].tag;36 t[rt].tag=0;37 }38 }39 void add(int L,int R,int v,int l,int r,int rt){40 if(t[rt].tag)pushdown(l,r,rt);41 if(L<=l && r<=R){42 t[rt].tag+=v;43 t[rt].sum+=v;44 return;45 }46 int mid=(l+r)>>1;47 if(L<=mid)add(L,R,v,ls);48 if(R>mid)add(L,R,v,rs);49 t[rt].sum=max(t[rt<<1].sum,t[rt<<1|1].sum);50 return;51 }52 void read(){53 scanf("%d%d",&n,&m);54 int i,j;55 for(i=1;i<=n;i++)scanf("%d",&f[i]);56 for(i=1;i<=m;i++)scanf("%d",&w[i]);57 return;58 }59 int main(){60 read();61 int i,j;62 for(i=n;i;i--){63 next[i]=last[f[i]];64 last[f[i]]=i;65 }66 for(i=1;i<=m;i++){67 if(last[i]){68 if(!next[last[i]])add(last[i],n,w[i],1,n,1); 69 else add(last[i],next[last[i]]-1,w[i],1,n,1);70 }71 }72 LL ans=0;73 for(i=1;i<=n;i++){74 ans=max(ans,t[1].sum);75 int tmp=next[i];76 if(tmp){77 add(i,tmp-1,-w[f[i]],1,n,1);78 if(next[tmp])add(tmp,next[tmp]-1,w[f[i]],1,n,1); 79 else add(tmp,n,w[f[i]],1,n,1);//如果之后没有相同电影了，从next[i]到n的区间都加值 80 }81 else add(i,n,-w[f[i]],1,n,1);//删除上一个区间的值 82 }83 printf("%lld",ans);84 return 0;85 }
Bzoj3747 [POI1015] Kinoman
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。