首页 > 代码库 > bzoj3550: [ONTAK2010]Vacation&&1283: 序列
bzoj3550: [ONTAK2010]Vacation&&1283: 序列
给出一个长度为 的正整数序列Ci，求一个子序列，使得原序列中任意长度为 的子串中被选出的元素不超过K(K,M<=100) 个，并且选出的元素之和最大。
据说是什么经典区间带权限制问题？
有两种写法...
1.可以根据流量平衡列方程，然后添加一个变量将不等式化成等式。具体看NOI2008的志愿者招募。
2.直接每个点依次排开，i->i+1连（k,0）【k是流量限制,0是费用】的边，然后对于一个区间[l,r]就l->r连（1,val）；然后源点->1连（k,0）,n->T一样，跑一边最大费用最大流即可。经过每个点的流量都保证了不超过k
#include<bits/stdc++.h>#define rep(i,l,r) for(int i=l;i<=r;++i)using namespace std;const int N=10240,inf=214748364;struct Edge{ int to,next,from,c,w;}e[1000000];int head[N],tot=1,ans,dis[N],from[N],m,K,n,T,x;bool used[N];inline void ins(int u,int v,int w,int cost) { e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].c=cost; e[tot].from=u;}inline bool spfa() { queue<int> q; rep(i,0,T) dis[i]=-1,from[i]=0,used[i]=0; dis[0]=1; q.push(0); used[0]=1; while(!q.empty()) { int x=q.front(); q.pop(); used[x]=0; for(int k=head[x];k;k=e[k].next) if(e[k].w>0&&dis[x]+e[k].c>dis[e[k].to]){ dis[e[k].to]=dis[x]+e[k].c; from[e[k].to]=k; if(!used[e[k].to]) { used[e[k].to]=1; q.push(e[k].to); } } } return dis[T]!=-1;}inline void run(){ int x=inf; for(int k=from[T];k;k=from[e[k].from]) x=min(x,e[k].w); for(int k=from[T];k;k=from[e[k].from]) { e[k].w-=x; e[k^1].w+=x; ans+=e[k].c*x; }}inline void insert(int u,int v,int w,int c){ ins(u,v,w,c); ins(v,u,0,-c);}int main(){ scanf("%d%d",&m,&K); n=m*3; T=n+1; rep(i,1,n) { scanf("%d",&x); insert(i-1,i,K,0); if(i+m<=n) insert(i,i+m,1,x);else insert(i,T,1,x); } insert(n,T,K,0); while(spfa()) run(); printf("%d\n",ans);}
bzoj3550: [ONTAK2010]Vacation&&1283: 序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。