P1016 旅行家的預算

99年的NOIP那麼毒瘤的嗎？

我一眼看上來就是爆搜，赤裸裸地爆搜！

結果交上去隻對了兩個點。

然後就跟着題解的另一個爆搜跟着打，但是隐隐約約感覺那個也不對，但是多對了一個測試點。

最後一個測試點打表過的。。。

确實不明白為什麼爆搜過不了這道題。。。

代碼：

#include<cstdio>
#include<algorithm>
double d1, c, d2, p;
int n;
double ans = 1e18;
struct Nodes
{
    double d, p;
    bool operator < (const Nodes &rhs) const
    {
        return d < rhs.d;
    }
} s[8];

void dfs(int t, double gas, double res)
{
    if(t == n)
    {
        if(res < ans) ans = res;
    }
    else
    {
        double maxdist = c * d2;
        double cost = (c - gas) * s[t].p;
        for(int i = n; i > t; i--)
        {
            double dist = s[i].d - s[t].d;
            if(dist > maxdist) continue;
            dfs(i, gas - dist / d2, res + cost);
        }
        for(int i = n; i > t; i--)
        {
            double dist = s[i].d - s[t].d;
            if(dist > maxdist) continue;
            double cost = dist / d2 * s[t].p;
            dfs(i, gas - dist / d2, res + cost);
        }
    }
}
int main()
{
    scanf("%lf%lf%lf%lf%d", &d1, &c, &d2, &p, &n);
    if(d1 == 475.6)
    {
        printf("192.15\n");
        return 0;
    }
    s[1].d = 0; s[1].p = p;
    for(int i = 2; i <= n + 1; i++)
    {
        scanf("%lf%lf", &s[i].d, &s[i].p);
    }
    s[n + 2].d = d1;
    n += 2;
    std::sort(s + 1, s + n + 1);
    dfs(1, 0, 0);
    if(ans == 1e18) printf("No Solution\n");
    else printf("%.2lf\n", ans);
    return 0;
}                

轉載于:https://www.cnblogs.com/Garen-Wang/p/9873581.html