记录编号	199479	评测结果	AAAAA
题目名称	[NOI 1999]01串	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-10-26 20:43:50	内存使用	0.35 MiB

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstdio>
 
using namespace std;
typedef vector<long long> vll;
 
const long long MAXN(1010), INF(LLONG_MAX / 3);
vll g[MAXN], c[MAXN];
long long n, a0, b0, l0, a1, b1, l1, d[MAXN], gnq[MAXN] = {0};
inline void addedge(long long, long long, long long), write();
inline bool spfa(long long);
queue<long long> q;
bool inq[MAXN] = {false};
 
main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	cin >> n >> a0 >> b0 >> l0 >> a1 >> b1 >> l1;
	
	for (long long i = 0; i <= n; ++i) {
		addedge(n + 1, i, 0);	//The number's dick exploded!
		if (i < n) {
			addedge(i + 1, i, 0);
			addedge(i, i + 1, 1);
		}
		if (i - l1 >= 0) {
			addedge(i - l1, i, b1);
			addedge(i, i - l1, -a1);
		}
		if (i - l0 >= 0) {
			addedge(i, i - l0, b0 - l0);
			addedge(i - l0, i, l0 - a0);
		}
	}
	
	if (spfa(n + 1))
		write();
	else
		cout << -1;
//	for (; ; );
}
 
inline void addedge(long long fr, long long to, long long cst){
	g[fr].push_back(to);
	c[fr].push_back(cst);
}
 
inline bool spfa(long long st) {
	q.push(st);
	inq[st] = true;
	++gnq[st];
	fill(d, d + n + 2, INF);
	d[st] = 0;
	while (! q.empty()) {
		long long u = q.front();
		q.pop();
		inq[u] = false;
		for (long long i = 0; i < g[u].size(); ++i)
			if (d[g[u][i]] > d[u] + c[u][i]) {
				d[g[u][i]] = d[u] + c[u][i];
				if (! inq[g[u][i]]) {
					inq[g[u][i]] = true;
					++gnq[g[u][i]];
					q.push(g[u][i]);
					if (gnq[g[u][i]] >= n + 1)
						return false;
				}
			}
	}
	return true;
}
 
inline void write() {
	for (long long i = 1; i <= n; ++i)
		cout << d[i] - d[i - 1];
}