「POJ1147」The Buses

传送门
Vjudge

解题思路

可以实现预处理一下可能成为一条线路的所有方案，然后把这些可能的方案按照长度降序排序，即按照路线上的时间节点从多到少排序。
加一个剪枝：
如果当前花费加上未来的最少的花费不会优，就直接return掉。

细节注意事项

• ans的初始化最好只要开到17，不然会跑得慢一些

参考代码

#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\)