状压dp 求调
  • 板块P1433 吃奶酪
  • 楼主GaoKui
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/26 11:07
  • 上次更新2023/10/27 01:27:31
查看原帖
状压dp 求调
676452
GaoKui楼主2022/11/26 11:07

WA了几个点,看不出来问题在哪

#include <bits/stdc++.h>

using namespace std;

const int MAX = 17;

int n; 
pair<double, double> arr[MAX];
double ans = INFINITY; // ans初始化为无限大

double dis_all[MAX][MAX]; // 相当于邻接矩阵
double dp[MAX][1 << MAX]; // 用于状压dp

double dis(const pair<double, double> &a, const pair<double, double> &b) // 计算两点间的距离
{
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int i, j;

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }

    memset(dis_all, 127, sizeof(dis_all)); // 初始化邻接矩阵中所有距离为正无穷
    memset(dp, 127, sizeof(dp)); // 初始化dp数组中所有距离为正无穷

    for (i = 0; i <= n; i++) // 处理出每个点到其余所有点的距离
    {
        for (j = 0; j < i; j++)
        {
            dis_all[i][j] = dis_all[j][i] = dis(arr[i], arr[j]);
        }
    }

    for (i = 1; i <= n; i++) // 初始化从原点直接到每个奶酪的状态
    {
        dp[i][1 << (i - 1)] = dis_all[0][i];
    }

    for (int k = 1; k < (1 << n); k++) // 枚举每个二进制状态
    {
        for (i = 1; i <= n; i++) // 枚举终点
        {
            if (k & (1 << (i - 1)) == 0) // 如果当前状态不包含该终点则跳过
            {
                continue;
            }
            for (j = 1; j <= n; j++) // 枚举起点
            {
                if (i == j || (k & (1 << (j - 1)) == 0)) // 如果当前状态不包含该起点,或起点终点一样则跳过
                {
                    continue;
                }

                dp[i][k] = min(dp[i][k], dp[j][k - (1 << (i - 1))] + dis_all[j][i]); // 状态转移方程
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        // cout << dp[i][(1 << n) - 1] << '\n';
        ans = min(ans, dp[i][(1 << n) - 1]);
    }

    cout << fixed << setprecision(2) << ans;
    // printf("%.2lf", ans);

    return 0;
}
2022/11/26 11:07
加载中...