求助站外状态压缩题
  • 板块题目总版
  • 楼主纯白
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/27 12:53
  • 上次更新2023/10/27 05:38:53
查看原帖
求助站外状态压缩题
327139
纯白楼主2022/10/27 12:53

原题在这
题目大意是在一个直角坐标系内,出生在原点,给n,m个点,前n个点需要全部踩过一次,然后回到原点。剩下那m个点,可踩可不踩,但是经过后速度翻倍(只有第一次经过算数),初速速度为1。求最短时间。
1 \leq n \leq 12
0 \leq m \leq 5
坐标x,y的绝对值均小于10000.
给出的坐标不重合,而且不为原点

这是我的代码,wa了一个点wawa


#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 18;
const double inf = 1e18;

struct node
{
    int x, y;
    node(int a, int b) : x(a), y(b) {}
    node() {}
} p[maxn];

double dp[maxn][1 << maxn];
double dis[maxn][maxn];

double dist(node a, node b)
{
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

int n, m;

int cntt(int s)
{
    int cnt = 0;
    s >>= n;
    for (int i = 0; i < m; i++)
    {
        if (s & (1 << i))
            ++cnt;
    }
    return cnt;
}

int judge(int s)
{
    for (int i = 0; i < n; i++)
    {
        if (!(s & (1 << i)))
            return false;
    }
    return true;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;

    int sum = m + n;

    for (int i = 0; i < sum; ++i)
    {
        cin >> p[i].x >> p[i].y;
    }

    for (int i = 0; i < sum; ++i)
        for (int j = i + 1; j < sum; ++j)
            dis[i][j] = dis[j][i] = dist(p[i], p[j]);

    for (int i = 0; i < sum; ++i)
        for (int s = 0; s < (1 << sum); ++s)
            dp[i][s] = inf;

    for (int i = 0; i < n + m; ++i)
        dp[i][1 << i] = dist(node(0, 0), p[i]);

    double minx = inf;

    for (int s = 1; s < (1 << sum); ++s)
        for (int i = 0; i < sum; ++i)
        {

            if (s & (1 << i))
            {
                int v = pow(2, __builtin_popcount(s >> n));
                bool flag = judge(s);

                for (int j = 0; j < sum; j++)
                {
                    if (i != j && (1 << j) & s)
                    {
                        if (i >= n)
                            v /= 2;
                        dp[i][s] = min(dp[i][s], dp[j][s - (1 << i)] + dis[i][j] / v);
                        if (i >= n)
                            v *= 2;
                        if (flag)
                            minx = min(minx, dp[i][s] + dist(p[i], node(0, 0)) / v);
                    }
                }
            }
        }

    cout << fixed << setprecision(10) << minx;
    return 0;
}
2022/10/27 12:53
加载中...