图论 差分约束 P5751题解
天哪，我居然能当上这道题的第一个题解!
这道题其实就是说0的数量和1的数量。让我们用一下类型前缀和的思想，d[i]表示前i个字符的1的个数。则有：
b1>=d[i]-d[i-l1]>=a1
l0-b0<=d[i]-d[i-l0]<=l0-a0//因为要多于那么多个0相当于少于那么多个1于是我们就可以愉快地差分约束啦~
贴代码：
#include<iostream>
#include<queue>
using namespace std;
int n,cnt,a0,a1,b0,b1,l0,l1,h[1005],d[1005],a[1005];bool f[1005];
class Edge{public:int to,nx,data;}e[4005];queue<int>q;
inline void Add(int x,int y,int z){e[++cnt]={y,h[x],z};h[x]=cnt;}
int main()
{
int i;cin>>n>>a0>>b0>>l0>>a1>>b1>>l1;
for(i=1;i<=n;i++)Add(i,i-1,0),Add(i-1,i,1);Add(n+1,0,0);
for(i=l0;i<=n;i++)Add(i,i-l0,b0-l0),Add(i-l0,i,l0-a0);
for(int i=l1;i<=n;i++)Add(i,i-l1,-a1),Add(i-l1,i,b1);
q.push(0);f[0]=true;for(i=1;i<=n;++i)d[i]=0x7fffffff;
while(!q.empty())
{
#define to e[i].to
int x=q.front();q.pop();f[x]=false;
for(i=h[x];i;i=e[i].nx)if(d[x]+e[i].data<d[to])
{
d[to]=d[x]+e[i].data;
if(++a[to]==n){cout<<-1;return 0;}
if(!f[to])f[to]=true,q.push(to);
}
}cout<<d[n];
}