传送门
从前，有一只懒猫叫CJB。每个小时，这只猫要么在睡觉，要么在吃东西，但不能一边睡觉一边吃东西，并且这只猫会在一整个小时干同一件事情。 对于接下来的 n n 个小时，CJB知道他在那nn个小时睡觉和吃东西的快乐值。 为了健♂康♀地生活，在任意的连续 k k 个整小时内，CJB要有至少 msms 小时睡觉，至少 me m e 个小时在吃东西。也就是说一共有 n−k+1 n − k + 1 段的 k k 小时需要满足上述条件。 你的任务是告诉CJB他接下来nn个小时能获得的最大快乐值是多少。
题解： 同志愿者招募， 记 xi x i 表示第 i i 小时是否睡觉，那么有： ms≤x1 x2 ... xk≤k−mems≤x1 x2 ... xk≤k−me
问题来了，我们不能对左右两边的等式分别按照原来的方法做，否则一个变量会出现在大于两个方程中出现，不过我们有巧妙的方法： 记 ti t i 为第 i i 个方程的松弛变量，先忽略左边的限制，则： x1 x2 ... xk t1=k−mex1 x2 ... xk t1=k−me 显然 t≥0 t ≥ 0 。 同时我们要让这个等式等价与 ms≤x1+x2+...+xk m s ≤ x 1 + x 2 + . . . + x k 解得 t≤k−ms−me t ≤ k − m s − m e
所以我们只需对志愿者招募进行一些改动使得松弛变量 0≤t≤k−ms−me 0 ≤ t ≤ k − m s − m e 。 然后跑最大费用流即可。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob) ? -1 : *ib++; } inline int rd() { char ch=nc(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();} return i*f; } const int N=1e5+50, M=2e6+50; const LL INF=0x3f3f3f3f3f3f3f; int n,k,ms,me,a[N],b[N]; int g[N],nt[M],vt[M],ec=1,src,des; LL dis[N],c[M],w[M]; int cur[N],vis[N],exi[N],vs; LL ans=0; inline void add(int x,int y,LL cc,LL ww) { nt[++ec]=g[x]; g[x]=ec; vt[ec]=y; c[ec]=cc; w[ec]=ww; nt[++ec]=g[y]; g[y]=ec; vt[ec]=x; c[ec]=0; w[ec]=-ww; } inline bool spfa() { static queue <int> q; for(int i=1;i<=des;i++) dis[i]=-INF; dis[src]=0; q.push(src); while(!q.empty()) { int u=q.front(); q.pop(); exi[u]=0; for(int e=g[u];e;e=nt[e]) { if(!c[e] || (dis[vt[e]]>=dis[u]+w[e])) continue; dis[vt[e]]=dis[u]+w[e]; if(!exi[vt[e]]) exi[vt[e]]=1, q.push(vt[e]); } } return dis[des]>-INF; } inline int dinic(int x,LL f,LL cost) { if(x==des) return ans+=cost*f, f; int rs=0; vis[x]=vs; for(int &e=cur[x];e;e=nt[e]) { if(!c[e] || vis[vt[e]]==vs || (dis[vt[e]]!=dis[x]+w[e])) continue; int o=dinic(vt[e],min(f-rs,c[e]),cost+w[e]); rs+=o; c[e]-=o; c[e^1]+=o; if(rs==f) return rs; } return dis[x]=-INF, rs; } inline void mcmf() { while(spfa()) { ++vs; memcpy(cur+1,g+1,sizeof(int)*des); while(dinic(src,INF,0)) ++vs, memcpy(cur+1,g+1,sizeof(int)*des); } } inline int out(int x) { if(x<=n-k) return x+1; return n-k+2; } inline int in(int x) { if(x<=k) return 1; return x-k+1; } int main() { n=rd(), k=rd(), ms=rd(), me=rd(); src=n-k+3; des=src+1; for(int i=1;i<=n;i++) a[i]=rd(); for(int i=1;i<=n;i++) b[i]=rd(), ans+=b[i]; for(int i=1;i<=n;i++) add(out(i),in(i),1,-b[i]+a[i]); for(int i=1;i<=n-k+1;i++) add(i+1,i,k-me-ms,0); add(1,des,k-me,0); add(src,n-k+2,k-me,0); cout<<(mcmf(),ans); }