BZOJ3136 [Baltic2013]brunhilda

决心写一道usaco之外的题，于是就挑中了这道。

为啥这编辑器有BUG，每次按回车要向下跳？

发现可以预处理DP。f_i表示第i个数被砍完需要最少多少刀。对于每一个i，设p_i是它的质因子里最大的一个在给定集合里的，那么它可以转移到(i+1,i+p_i)这个范围。然后f_i显然不减，所以用单调队列之类的玩意。

然后卡着时间限制过了。不知道前面那些秒跑的人是怎么搞的。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 10000009;
const int maxm = 100009;

int k[maxn], f[maxn], n, m, q, p[maxm], v[maxm];

void pre(int n) {
	sort(p, p + m);
	memset(k, 0, sizeof(k));
	for (int i = 0; i < m; ++ i)
		if (!i || p[i] != p[i - 1])
			for (int j = 0; j <= n; j += p[i])
				k[j] = p[i];

	static int q[maxn];
	int hd(0), tl(1);
	q[0] = f[0] = 0;
	for (int i = 1; i <= n; ++ i) {
		while (hd < tl && i >= q[hd] + k[q[hd]])
			++ hd;
		if (hd == tl) {
			f[i] = -1;
			continue;
		}
		f[i] = f[q[hd]] + 1;
		while (hd < tl && (f[i] < f[q[tl - 1]] || (f[i] == f[q[tl - 1]] && i + k[i] >= q[tl - 1] + k[q[tl - 1]])))
			-- tl;
		q[tl ++] = i;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &m, &q);
	memset(k, 0, sizeof(k));
	for (int i = 0; i < m; ++ i)
		scanf("%d", p + i);
	n = 0;
	for (int i = 0; i < q; ++ i) {
		scanf("%d", v + i);
		if (v[i] > n)
			n = v[i];
	}
	pre(n);
	for (int i = 0; i < q; ++ i)
		if (f[v[i]] == -1)
			puts("oo");
		else
			printf("%d\n", f[v[i]]);
}