记录编号	60027	评测结果	AAAAA
题目名称	[NOI 1999]01串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-05-15 21:24:41	内存使用	0.88 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=1010;
int N,A0,B0,L0,A1,B1,L1;
//长度N
class EDGE{
public:
	int b,t;
	EDGE(){b=t=0;}
};
deque<EDGE> c[SIZEN];
void addedge(int a,int b,int t){
	EDGE temp;
	temp.b=b,temp.t=t;
	c[a].push_back(temp);
}
void read(void){
	scanf("%d%d%d%d%d%d%d",&N,&A0,&B0,&L0,&A1,&B1,&L1);
	int i;
	for(i=0;i+L0<=N;i++){//S0(i+L0)-S0(i)∈[A0,B0]
	//有一条边从i指向i+L0权值为A0,另一条边从i+L0指向i权值为-B0
		addedge(i,i+L0,A0);
		addedge(i+L0,i,-B0);
	}
	for(i=0;i+L1<=N;i++){//S0(i+L1)-S0(i)∈[L1-B1,L1-A1]
	//有一条边从i指向i+L1权值为L1-B1,另一条边从i+L1指向i权值为A1-L1
		addedge(i,i+L1,L1-B1);
		addedge(i+L1,i,A1-L1);
	}
	for(i=0;i<=N;i++) addedge(N+1,i,0);
	for(i=0;i<N;i++) addedge(i,i+1,0),addedge(i+1,i,-1);
}
int f[SIZEN]={0};
const int MIN=-0x7fffffff;
bool SPFA(int s){
	deque<int> Q;
	int tp[SIZEN]={0};//入队次数
	bool inq[SIZEN]={0};//是否在队里
	int x,i,y;
	for(i=0;i<=N;i++) f[i]=MIN;
	Q.push_back(s);tp[s]=1;f[s]=0;inq[s]=true;
	while(Q.size()){
		x=Q.front();Q.pop_front();inq[x]=false;
		for(i=0;i<(int)c[x].size();i++){
			y=c[x][i].b;
			if(tp[y]==N+1){//正环
				return false;
			}
			if(f[x]+c[x][i].t>f[y]){
				f[y]=f[x]+c[x][i].t;
				if(!inq[y]){
					Q.push_back(y);
					inq[y]=true;tp[y]++;
				}
			}
		}
	}
	return true;
}
int a[SIZEN]={0};
void write(void){
	int i;
	for(i=1;i<=N;i++) printf("%d",1-(f[i]-f[i-1]));
	printf("\n");
}
int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	read();
	if(SPFA(N+1)) write();
	else printf("-1\n");
	return 0;
}