「POJ1147」The Buses

解题思路

可以首先预处理一下可能成为一条线路的所有方案，然后把这些可能的方案按照长度降序排序，即按照路线上的时间节点从多到少排序。

因为这样我们就可以先确定更多的时刻的状态，减少搜索深度。

然后加一个最优化剪枝：

如果当前花费加上未来的最少的花费不会优，就直接return掉。

然后因为我们把所有的路线都按照路上节点数降序排序，所以我们只要碰到第一个不会更优的就直接return。

细节注意事项

ans的初始化最好只要开到17，不然会跑得慢一些
然后在 vjudge 或 POJ 上交的时候，要选的语言是 G++ 而不是 C++ 我居然CE了一次

Main.cpp

F:\temp\21004851.198535\Main.cpp(51) : error C2059: syntax error : '{'

F:\temp\21004851.198535\Main.cpp(51) : error C2143: syntax error : missing ';' before '{'

F:\temp\21004851.198535\Main.cpp(51) : error C2065: 'j' : undeclared identifier

F:\temp\21004851.198535\Main.cpp(51) : error C2065: 'j' : undeclared identifier

F:\temp\21004851.198535\Main.cpp(51) : error C2143: syntax error : missing ';' before '}'

题面确实有点点的难捋清楚啊。。。

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= c == '-', c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 1926;

int n, cnt[70], ans = 17, X;

struct node { int a, b, c; } t[_];

inline bool cmp(const node& x, const node& y) { return x.c > y.c; }

inline bool check(int a, int b) {

	for (rg int i = a; i < 60; i += b)

		if (!cnt[i]) return 0;

	return 1;

}

inline void dfs(int i, int num) {

	if (n == 0) { ans = min(ans, num); return ; }

	for (rg int j = i; j <= X; ++j) {

		if (num + n / t[j].c >= ans) return ;

		if (check(t[j].a, t[j].b)) {

			for (rg int k = t[j].a; k < 60; k += t[j].b) --n, --cnt[k];

			dfs(j, num + 1);

			for (rg int k = t[j].a; k < 60; k += t[j].b) ++n, ++cnt[k];

		}

	}

}

int main() {

#ifndef ONLINE_JUDGE

 	freopen("in.in", "r", stdin);

#endif

	read(n);

	for (rg int x, i = 1; i <= n; ++i) read(x), ++cnt[x];

	for (rg int i = 0; i < 30; ++i) {

		if (!cnt[i]) continue;

		for (rg int j = i + 1; i + j < 60; ++j)

			if (check(i, j)) t[++X] = (node) { i, j, (59 - i) / j + 1 };

	}

	sort(t + 1, t + X + 1, cmp);

	dfs(1, 0);

	printf("%d\n", ans);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「POJ1147」The Buses

解题思路

细节注意事项

参考代码

最新文章

热门文章