p1433

AA12_G · 2025-02-28 18:43:42 · 个人记录

状压大炮。

一眼大炮。“状压”型号的大炮的制动方式很复杂，主要是根据二进制这一位上面是 0 或 1 来决定发射炮弹的型号。顾名思义，炮弹型号 f_{i,k} 就代表二进制为 k 时走到点 i 的炮弹。所以有 f_{i,k} =\min (f_{i,k},f_{j,k-2^{i-1}}+a_{i,j})。（a 数组表示两点间的距离）最后找出 \max(f_{i,2^n-1}) 中间的最大值就行。

代码也是很简单……个蛋！

#include <bits/stdc++.h>
double dis[20][20];
double x[20], y[20];
double f[20][100010];
int n;
double diss(int v, int w)
{
    return sqrt((x[v] - x[w]) * (x[v] - x[w]) + (y[v] - y[w]) * (y[v] - y[w]));//算距离
}
int main()
{
    double ans;
    for (int i = 0; i < 20; i ++) for (int j = 0; j < 100010; j ++) f[i][j] = 1e9;
    ans = f[0][0];
    cin >> n
    for(int i = 1; i <= n; i ++)
    {
        cin >> x[i] >> y[i];
    }
    x[0] = 0; y[0] = 0;
    for(int i = 0; i <= n; i ++)
    {
        for(j = i + 1; j <= n; j ++)
        {
            a[i][j] = diss(i, j);
            a[j][i] = a[i][j];
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        f[i][(1 << (i - 1))] = a[0][i];
    }
    for(int k=1; k < (1 << N); k ++)
    {
        for(int i = 1; i <= n; i ++)
        {
            if((k & (1 << (i - 1))) == 0)//i压根没走过不可能成为当前走到的点
                continue;
            for(int j = 1; j <= n; j ++)
            {
                if(i == j)//一样的话等于自己走到自己，wyy
                    continue;
                if((k & (1 << (j - 1))) == 0)//j 没走自然不可能走到 i
                    continue;
                f[i][k] = min(f[i][k], f[j][k - (1 << (i - 1))] + a[i][j]);
            }
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        ans = min(ans, f[i][(1 << N) - 1]);
    }
    printf("%.2f\n", ans);
}