诡异状压DP求助
  • 板块P1433 吃奶酪
  • 楼主Tibrella
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/2/22 17:10
  • 上次更新2023/10/24 00:06:33
查看原帖
诡异状压DP求助
655192
Tibrella楼主2023/2/22 17:10
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>

using std::cerr;
using std::cin;
using std::cout;

const char endl = '\n';
const int N = 16;
constexpr int ST = 1 << N;

template <typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

#define count(num) __builtin_popcount(num)
#define get_dis(n1, n2) sqrt((x[n1] - x[n2]) * (x[n1] - x[n2]) + (y[n1] - y[n2]) * (y[n1] - y[n2]))

int n;
double f[N][ST];
double dis[N][N];
double x[N], y[N];
int suc;

int main() {
    memset(f, 0x42, sizeof f);
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= n; ++i) {
        suc |= (1 << i - 1);
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            dis[i][j] = get_dis(i, j);
        }
    }

    for (int i = 1; i <= n; ++i) {
        f[i][1 << i - 1] = dis[0][i];
    }
    // for (int cnt = 0; cnt < 10; ++ cnt)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i ^ j)
                for (int s = 0; s <= 1 << n; ++s) {
                    int fix = 1 << j - 1;
                    if (!(s & fix)) {
                        f[j][s | fix] = min(f[j][s | fix], f[i][s] + dis[i][j]);
                    }
                }
        }
    }
    

    double ans = 0xffffffff;
    for (int i = 0; i <= n; ++i) {
        ans = min(ans, f[i][suc]);
    }
    cout << std::fixed << std::setprecision(2) << ans;

    // for (int i = 0; i <= 1<<n+1; ++ i) {
    //     cout << f[n+1][i] << endl;
    // }

    // for (int i = 0; i <= n; i ++)
    // {
    //     for (int j = 0; j < (1 << n); j ++)
    //         cerr << f[i][j] << " ";
    //     cerr << endl;
    // }

    return 0;
}

以上是我一开始的代码,只得了 40 pts
然后我发现 i,ji,j 正序倒序枚举结果不同,就不知道为啥写了注释掉的那一行 for (int cnt = 0; cnt < 10; ++ cnt),把 dp 数组迭代了不同次数,分别拿到了 60 70 80 的好成绩,最后调成 10 次切掉了本题

所以各位大佬能帮忙看看我原做法错在哪里了吗(

2023/2/22 17:10
加载中...