因为这两题有递进关系，所以放一起写
Problem
题意概要：一个长度为 (n) 的序列({c_i})，求一个子集，使得原序列中任意长度为 (m) 的子串中被选出的元素不超过(K)个，并且选出的元素之和最大。
bzoj 4842 Please contact lydsy2012@163.com! （可以下数据自测 然而还需要spj，upd：loj6079好像是一样的）
题意概要：构造一个长度为(n)的(12)序列({a_i})，(a_i=1)或(2)的贡献分别为(s_i,t_i)，对于任意长度为(k)的子串，至少要有(t_1)个(1)，至少要有(t_2)个(2)，问这(n)个小时的最大收益
Solution-bzoj1283
这题和网络流24题-最长(k)可重区间集问题很像，只不过这里运用了点线互换的套路。
限制对于每个区间选出的元素不能超过(k)个，等价于把元素视作一条长度为(k)的线段，每个点不能被覆盖超过(k)次
每个点被覆盖不超过(k)次就可以用网络流解决了，利用流量限制(k)
- 建立一个主轴（连边(i ightarrow i+1)，流量(inf)，费用(0)）用以传递流量
- 对每个点建出线段（连边(i ightarrow i+k)，流量(1)，费用(c_i)）
这样如果想取得一个权值(c_i)，必须有(1)的流量从(i)开始走费用为(c_i)的那条边，而只要设置源点流量为(k)，则对于每个截面的流量不会超过(k)，化为实际意义即每个点被覆盖不超过(k)次，跑最大费用最大流即可
Solution-bzoj4842
简化题目
现将这题的 “二者选其一” 转化为上一题的 “选与不选”：先假定序列全部选(2)，再考虑对于每个位置换不换成(1)（(ans=sum e_i)，令(n)个点权值为(a_i=s_i-e_i)，考虑每个点选与不选）
上一题是每个点被覆盖不超过(k)次
考虑这题变成了交换，设交换(x)次，则选择(x)个(1)，选择(k-x)个(2)，由于(t_1leq x\t_2leq k-x)，即(t_1leq xleq k-t_2)
即每个点被覆盖不超过(k-t2)次，不少于(t_1)次，不多于(k-t_2)次，上下界网络流……
然而凑巧的是，前天我刚想到一个奇妙的下界网络流方法 实际很简单，比如要一个一条边的流量大于等于某个数(t)，则只要往这条边的入度注满(s)的流，然后在入度处拉出一条流量上界为(s-t)的边，则原边流量刚好大于等于(t)（即利用限制分流保证原边流量下界）
所以这题就可以做了，类似于上一题，这里不能被覆盖超过(k-t_2)次，即源点流量为(k-t_2)，不少于(t_1)次，利用上面这个方法就是将主轴的流量上界设定为(k-t_2-t_1)，这样对于每个点都会至少有((k-t_2)-(k-t_2-t_1)=t_1)次覆盖了
但是考虑若像上一题那样源点只连第一个位置，会使得前面(k)个点之间的主轴承受不住，所以需要源点需要往前(k)个点都连一条无限流量无费用的边
细化做法：
- 虚源点往源点连边（流量(k-t_2)，费用(0)）
- 源点往(i,iin[1,k])连边（流量(inf)，费用(0)）
- (i)往(i+1)连边（流量(k-t_1-t_2)，费用(0)）
- (i)往(i+k)连边，若(i+k>n)则连向(t(t=n+1))（流量(1)，费用(s_i-e_i)）
跑最大费用最大流即可
哦，对了，听说这两题还可以线性规划玩
Code
bzoj1283
#include <bits/stdc++.h>
using namespace std;
inline int read(int&x){
char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;
}
const int N=4050,inf = 0x3f3f3f3f;
struct Edge{int v,w,c,nxt;}a[N];
int head[N],n,m,s,t,k,_;
inline void add(int u,int v,int w,int c){
a[_].v=v,a[_].w=w,a[_].c=c,a[_].nxt=head[u],head[u]=_++;
a[_].v=u,a[_].w=0,a[_].c=-c,a[_].nxt=head[v],head[v]=_++;
}
namespace max_cost{
int q[N*10],he,ta;
int dis[N],inq[N],vis[N],dfc=0;
bool bfs(){
for(int i=0;i<t;++i)dis[i]=-inf,inq[i]=0;
dis[q[he=ta=1]=t]=0,inq[t]=1;
int x;while(he<=ta){
inq[x=q[he++]]=0;
for(int i=head[x];~i;i=a[i].nxt)
if(a[i^1].w>0&&dis[a[i].v]<dis[x]-a[i].c){
dis[a[i].v]=dis[x]-a[i].c;
if(!inq[a[i].v])q[++ta]=a[i].v,inq[a[i].v]=1;
}
}return dis[s]!=-inf;
}
int dfs(int x,int flw){
if(x==t||!flw)return flw;
int res=0,tmp;vis[x]=dfc;
for(int i=head[x];~i;i=a[i].nxt)
if(vis[a[i].v]!=dfc && a[i].w>0 && dis[a[i].v]==dis[x]-a[i].c)
if(tmp=dfs(a[i].v,min(flw-res,a[i].w))){
a[i].w-=tmp,a[i^1].w+=tmp,res+=tmp;
if(res==flw)return res;
}
return res;
}
void main(){
int flw,ans=0;
while(bfs())
for(vis[t]=dfc;vis[t]==dfc;){
++dfc;flw=dfs(s,inf);
ans+=flw*dis[s];
}
printf("%d
",ans);
}
}
int main(){
read(n),read(m),read(k);s=0,t=n+1;
for(int i=0;i<=t;++i)head[i]=-1;
add(s,1,k,0);
for(int i=1,x;i<=n;++i){
add(i,i+1,inf,0);
add(i,min(i+m,t),1,read(x));
}
max_cost::main();
return 0;
}
bzoj4842
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename _Tp> inline _Tp read(_Tp&x){
char c11=getchar(),ob=0;x=0;
while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')ob=1,c11=getchar();
while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}
const int N=1010,M=8010,flow_inf = 0x3f3f3f3f;
struct Edge{int v,w,c,nxt;}a[M];
int head[N],sv[N],ev[N],id[M],state[N];
int n,k,t1,t2;
int s,t,ss,_;
ll ans;
inline void add(int u,int v,int w,int c){
a[_].v=v,a[_].w=w,a[_].c=+c,a[_].nxt=head[u],head[u]=_++;
a[_].v=u,a[_].w=0,a[_].c=-c,a[_].nxt=head[v],head[v]=_++;
}
namespace max_cost{
const ll dis_inf = 0x3f3f3f3f3f3f3f3f;
int q[N*170],inq[N],vis[N];
int he,ta,dfc=0;
ll dis[N];
bool bfs(){
for(int i=t;i;--i)inq[i]=0,dis[i]=-dis_inf;
dis[q[he=ta=1]=t]=0,inq[t]=true;
int x;
while(he<=ta){
inq[x=q[he++]]=false;
for(int i=head[x];~i;i=a[i].nxt)
if(a[i^1].w>0 && dis[a[i].v]<dis[x]-a[i].c){
dis[a[i].v]=dis[x]-a[i].c;
if(!inq[a[i].v])inq[q[++ta]=a[i].v]=true;
}
}return dis[s]!=-dis_inf;
}
int dfs(int x,int flw){
if(x==t||!flw)return flw;
int res(0),tmp;vis[x]=dfc;
for(int i=head[x];~i;i=a[i].nxt)
if(vis[a[i].v]!=dfc && a[i].w>0 && dis[a[i].v]==dis[x]-a[i].c)
if(tmp=dfs(a[i].v,min(flw-res,a[i].w))){
a[i].w-=tmp,a[i^1].w+=tmp,res+=tmp;
if(res==flw)return res;
}
return res;
}
void main(){
int flw;
while(bfs())
for(vis[t]=dfc;vis[t]==dfc;){
++dfc;flw=dfs(s,flow_inf);
ans+=flw*dis[s];
}
printf("%lld
",ans);
}
}
int main(){
scanf("%d%d%d%d",&n,&k,&t1,&t2);
s=n+1,ss=n+2,t=n+3;
for(int i=t;i;--i)head[i]=-1;
add(s,ss,k-t2,0);
for(int i=1;i<=n;++i)scanf("%d",sv+i);
for(int i=1;i<=n;++i)scanf("%d",ev+i),ans+=ev[i];
for(int i=1;i<=k;++i)add(ss,i,flow_inf,0);
for(int i=1;i<=n;++i){
add(i,i+1>n?t:i+1,k-t1-t2,0);
add(i,i+k>n?t:i+k,1,sv[i]-ev[i]);
id[_-1]=i;
}
max_cost::main();
for(int i=0;i<_;++i)
if(id[i])
state[id[i]]=(a[i].w>0);
for(int i=1;i<=n;++i)putchar(state[i]?'S':'E');
putchar('
');return 0;
}