自动搬运

查看原文

来自洛谷，原作者为

	Prean 不断倒下，不断站起来，不停地与自己作斗争

搬运于2025-08-24 22:14:02，当前版本为作者最后更新于2020-03-13 21:46:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

天哪，我居然能当上这道题的第一个题解!

这道题其实就是说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];
}