核心算法：差分约束，前缀和
重点：如何灵活构图来应用差分约束算法。
准备工作：
设(x_i)为字符串(S)的子串：(s_1...s_i)中(1)的个数。
（前缀和）
那么(x_i-x_{i-L})所表达的含义即为：(S)的子串：(s_{i-L+1}...s_i)中(1)的个数。
（(Lleq i leq n)）（(L)为子串长度，(n)为(S)的长度）
因为，(S)只由(0,1)组成，所以(l-left(x_i-x_{i-L} ight)) 即为：(S)的子串：(s_{i-L+1}...s_i)中(0)的个数。
差分约束：
我们将字符串的前缀和(x_i)当作图中的节点，利用差分约束，先求出一组可行解。
根据题意，我们可以得出：
(A_1 leq x_i-x_{i-L_1} leq B_1)
(A_0-L_0 leq x_{i-L_0}-x_i leq B_0-L_0)
至此，构图还没有结束。
因为，(S)是一个连续的序列，题目中有一个隐藏的关系：
(0 leq x_i-x_{i-1} leq 1)
（同时，因为该关系使图中存在了一个点，使其连通了其余各点，构造超级源点的工作也省去了。）
细节：
由于差分约束的多解性，为了使其满足可行解最大。
不妨设想，(x_1)可行解的最大值是1，所以，我们只要让(x_1=1)，那么，整体的值就最大。
同时，也因为，我们所求的是前缀和，存在单调性。(x_n geq x_1)。
所以得到最后答案为：(x_n-x_1+1)。
（这里我不认为是单单减去(x_0)，虽然说，要求(x_0)最大只能是(0)，但是不能确保当(x_0=0)时，(x_1=1)。）
代码如下：
#include <bits/stdc++.h>
#define MAXN 500000
#define INF 0x3f3f3f3f
using namespace std;
int adj[MAXN],cnt=0;
int n,a0,b0,l0,a1,b1,l1;
struct EDGE { int to,nxt,val; } e[MAXN];
void addedge(int u,int v,int w) { e[++cnt].to=v; e[cnt].val=w; e[cnt].nxt=adj[u]; adj[u]=cnt; }
int dis[MAXN],vis[MAXN],num[MAXN];
queue < int > q;
bool SPFA()
{
for(int i=1;i<=n;++i) {dis[i]=INF;}
dis[0]=0; vis[0]=1; ++num[0]; q.push(0);
while(!q.empty())
{
int u=q.front(); q.pop(); vis[u]=0;
for(int i=adj[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].val)
{
dis[v]=dis[u]+e[i].val;
if(!vis[v])
{
++num[v]; if(num[v]>=n) return 0;
q.push(v); vis[v]=1;
}
}
}
}
return 1;
}
int main()
{
scanf("%d%d%d%d%d%d%d",&n,&a0,&b0,&l0,&a1,&b1,&l1);
for(int i=1;i<=n;++i)
{
addedge(i,i-1,0);
addedge(i-1,i,1);
}
for(int i=l0;i<=n;++i)
{
addedge(i,i-l0,b0-l0);
addedge(i-l0,i,l0-a0);
}
for(int i=l1;i<=n;++i)
{
addedge(i,i-l1,-a1);
addedge(i-l1,i,b1);
}
if(SPFA()) printf("%d",dis[n]-dis[1]+1);
else printf("-1");
return 0;
}