BZOJ3136 [Baltic2013]brunhilda

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

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

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

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

1	#include <cstdio>
2	#include <cstring>
3	#include <algorithm>
4	
5	using namespace std;
6	
7	const int maxn = 10000009;
8	const int maxm = 100009;
9	
10	int k[maxn], f[maxn], n, m, q, p[maxm], v[maxm];
11	
12	void pre(int n) {
13		sort(p, p + m);
14		memset(k, 0, sizeof(k));
15		for (int i = 0; i < m; ++ i)
16			if (!i || p[i] != p[i - 1])
17				for (int j = 0; j <= n; j += p[i])
18					k[j] = p[i];
19	
20		static int q[maxn];
21		int hd(0), tl(1);
22		q[0] = f[0] = 0;
23		for (int i = 1; i <= n; ++ i) {
24			while (hd < tl && i >= q[hd] + k[q[hd]])
25				++ hd;
26			if (hd == tl) {
27				f[i] = -1;
28				continue;
29			}
30			f[i] = f[q[hd]] + 1;
31			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]])))
32				-- tl;
33			q[tl ++] = i;
34		}
35	}
36	
37	int main() {
38	#ifndef ONLINE_JUDGE
39		freopen("in.txt", "r", stdin);
40	#endif
41	
42		scanf("%d%d", &m, &q);
43		memset(k, 0, sizeof(k));
44		for (int i = 0; i < m; ++ i)
45			scanf("%d", p + i);
46		n = 0;
47		for (int i = 0; i < q; ++ i) {
48			scanf("%d", v + i);
49			if (v[i] > n)
50				n = v[i];
51		}
52		pre(n);
53		for (int i = 0; i < q; ++ i)
54			if (f[v[i]] == -1)
55				puts("oo");
56			else
57				printf("%d\n", f[v[i]]);
58	}
59