很好的建模题 首先变换一下 默认每天都sleep 那么eat的价值就是这一天两个值的差值 每 K 天eat的次数必须在[mine,maxe]之间 然后我们在变换一下 K 天这个区间[i−K 1,i]变成区间末尾 i 表示 第i天eat 能够对 [i,min(i+K−1,n)] 天都产生贡献 这样我们就得到了这样一个问题 选出某些区间 使得每个点 (K,K+1,K+2,⋯,n) 被覆盖 [mine,maxe] 次 使得选出来的区间代价最大
我们怎么用费用流解决呢 其实类似 [费用流] POJ 3680 Intervals 我们看官方题解
我的理解是 这个图的流必须是 maxe 对于主链上的一条边 (i,i+1)i≥K 那么 这个剖面的总流量是 maxe 然后因为 (i,i+1) 的流量是属于 [0,maxe−mine] 所以 跨过它的所有的有代价的边的流量是属于 [mine,maxe] 的 也就满足了题目限制
UPD.当时太naive，按照上下界直接建图，拆掉上下界之后就是这个图
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int M=10005; const int N=1005; struct edge{ int u,v,w,f,next; }G[M]; int head[N],inum=1; inline void add(int u,int v,int w,int f,int p){ G[p].u=u; G[p].v=v; G[p].w=w; G[p].f=f; G[p].next=head[u]; head[u]=p; } inline void link(int u,int v,int w,int f){ add(u,v,w,f,++inum),add(v,u,-w,0,++inum); } int S,SS,T; int Q[5000005],l,r; int ins[N],pre[N]; ll dis[N]; ll Mincost; #define V G[p].v inline bool SPFA(){ for (int i=1;i<=T;i++) ins[i]=0,pre[i]=0,dis[i]=1LL<<60; l=r=-1; Q[++r]=S; ins[S]=1; dis[S]=0; while (l<r){ int u=Q[++l]; ins[u]=0; for (int p=head[u];p;p=G[p].next) if (G[p].f && dis[V]>dis[u]+G[p].w){ dis[V]=dis[u]+G[p].w; pre[V]=p; if (!ins[V]) Q[++r]=V,ins[V]=1; } } if (dis[T]==1LL<<60) return 0; int minv=1<<30; for (int p=pre[T];p;p=pre[G[p].u]) minv=min(minv,G[p].f); Mincost+=(ll)minv*dis[T]; for (int p=pre[T];p;p=pre[G[p].u]) G[p].f-=minv,G[p^1].f+=minv; return 1; } int n,K,a[N]; ll Ans; int mins,mine,maxe; int main(){ int x; freopen("delight.in","r",stdin); freopen("delight.out","w",stdout); read(n); read(K); S=n+1,SS=n+2,T=n+3; read(mins); read(mine); maxe=K-mins; for (int i=1;i<=n;i++) read(x),a[i]-=x,Ans+=x; for (int i=1;i<=n;i++) read(x),a[i]+=x; for (int i=1;i<n;i++) link(i,i+1,0,maxe-mine); link(n,T,0,maxe-mine); int tmp=inum+1; for (int i=1;i<=n;i++) if (i+K<=n) link(i,i+K,-a[i],1); else link(i,T,-a[i],1); for (int i=1;i<=K;i++) link(SS,i,0,1<<30); link(S,SS,0,maxe); while (SPFA()); printf("%lld\n",Ans-Mincost); for (int i=1;i<=n;i++,tmp+=2) G[tmp].f?putchar('S'):putchar('E'); return 0; }